问题描述:给定一个由n行数字组成的数字梯形,如图8-3所示.梯形的第1行有m个数字.从梯形的顶部

的m个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径.

规则1:从梯形的顶至底的m条路径互不相交.

规则2:从梯形的顶至底的m条路径仅在数字结点处相交.

规则3:从梯形的顶至底的m条路径允许在数字结点处相交或在边处相交.

算法设计:对于给定的数字梯形,分别按照规则1、规则2和规则3计算出从梯形的顶至底的m条路径,使这m条路径经过的数字总和最大.

数据输入:由文件input,txt提供输入数据.文件的第1行中有2个正整数m和n(m,n≤20),分别表示数字梯形的第1行有m个数字,共有n行.接下来的n行是数字梯形中各行的数字.第1行有m个数字,第2行有m+1个数.....

结果输出:将按照规则1.规则2和规则3计算出的最大数字总和输出到文件output.txt每行一个最大总和.