4162: 数塔
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：2214
通过：660
题目描述
数字三角形，从三角形顶部往下走，只能往左下或右下走，求走到最下面时所经过的数字和最大为多少？（下图为n=6时的情况)
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
96 |
|
30 |
|
|
|
|
|
|
|
|
83 |
|
52 |
|
60 |
|
|
|
|
|
|
21 |
|
65 |
|
44 |
|
61 |
|
|
|
|
8 |
|
79 |
|
50 |
|
41 |
|
21 |
|
| 61 |
|
41 |
|
50 |
|
38 |
|
79 |
|
10 |
输入格式
第1行：整数n(1<=n<=1000)
第2-n+1行：每行若干整数，第i行有i-1个整数，空格分隔。
第2-n+1行：每行若干整数，第i行有i-1个整数，空格分隔。
输出格式
一行：一个整数，表示所经过数字的最大和。
输入样例 复制
6
2
96 30
83 52 60
21 65 44 61
8 79 50 41 21
61 41 50 38 79 10
输出样例 复制
375