11409: 数字三角形
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：3
Solved：0
Description
数字三角形，从三角形顶部往下走，只能往左下或右下走，求走到最下面时所经过的数字和最大为多少？（下图为n=6时的情况)
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
96 |
|
30 |
|
|
|
|
|
|
|
|
83 |
|
52 |
|
60 |
|
|
|
|
|
|
21 |
|
65 |
|
44 |
|
61 |
|
|
|
|
8 |
|
79 |
|
50 |
|
41 |
|
21 |
|
| 61 |
|
41 |
|
50 |
|
38 |
|
79 |
|
10 |
Input
第1行：整数n(1<=n<=1000)
第2-n+1行：每行若干整数，第i行有i-1个整数，空格分隔。
Output
一行：一个整数，表示所经过数字的最大和。
Sample Input Copy
6
2
96 30
83 52 60
21 65 44 61
8 79 50 41 21
61 41 50 38 79 10
Sample Output Copy
375