Description

如图所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径,使该路径所经过的数字总和最大。只要求输出总和。

1.   一步可沿左斜线向下或右斜线向下走；

2.   三角形行数小于等于100;

3.   三角形中的数字为0,1,…,99;

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Input Format

输入数据共n+1行，第一行为三角形行数n，后面n行表三角形每一行的数字。

Output Format

输出结果总和。

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

30