下图是个数字三角,请编写一个程序计算从顶部至底部某处一条路径,使得该路径所经过的数字总和最大。

7

3  8

8  1  0

2  7  4  4

1.  每一步可沿左斜线向下或右斜线向下走;

2.  1<=三角形行数<=100

3.  三角形中的数字为整数 0,1,……,99。

4.  如果有多种情况结果都最大,任意输出一种即可。

 

输入:

第一行一个整数N,代表三角形的行数。

接下来N行,描述了一个数字三角。

 

输出:

    第一行一个整数,代表路径所经过底数字总和。

    第二行N个数,代表所经过的数字。

 

样例:

输入:

4
7
3 8
8 1 0
2 7 4 4

输出:

25
7 3 8 7