题目描述

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

（1）一步可向下或沿右斜线向下走。

（2）三角形行数小于等于100

（3）三角形中的数字为0，1，...，99

输入

第一行n，表示行数 以下n行，第i行共有i个数

输出

共一行，一个数，表示数字总和的最大值

样例输入

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

样例输出

30