题目描述

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

上面显示了一个数字三角形。 写一个程序，计算从顶到下所有数字和最大的一条路径。需要注意的是，每次只能走向下或者右下的数字。

输入格式

第一行一个整数 N (N<=100)，表示三角形的高度。 接下来 N 行，每行 i 个整数，分别表示第 i 层的 i 个数。

输出格式

输出一行，为一个整数，表示路径和最大是多少。

样例

输入 #1复制

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出 #1复制

30