Problem1071--数塔

1071: 数塔

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 447  Solved: 273
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI在CSU的某个角落发现了一座金字塔,而且这座金字塔是由数字组成的(如下图所示),现在PIPI想到塔顶去看看,它可以从底层任意一个数字出发逐层爬上去。PIPI每次可以爬至上一层相邻的数字上。
现在PIPI想知道,它如何选择爬上去的路径,使该路径经过的数字和最大?


Input

多组数据
每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间[0,99]内。

Output

对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。

Sample Input

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

Sample Output

30

Source/Category