1783: 数字金字塔

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:3 Solved:2

Description

考虑在下面被显示的数字金字塔(第n行有n列)。写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每前进一步可以走到它的正下方或者右下方(往下一行、往右一列)的位置。

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

在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和:30

Input

第一个行包含 R(1<= R<=1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。

Output

输出仅一行,包含那个可能得到的最大的和。

Sample Input Copy

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

Sample Output Copy

30

Source/Category