数字三角形
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 Format
第1行：整数n(1<=n<=1000)第2-n+1行：每行若干整数，第i行有i-1个整数空格分隔。
Output Format
一行：一个整数，表示所经过数字的最大和。
6
2
96 30
83 52 60
21 65 44 61
8 79 50 41 21
61 41 50 38 79 10
375