时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有一个由非负整数组成的三角形，第1行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，如下图。从第1行开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的各数加起来，如何走才能使这个和最大。
　　　　　　

【输入格式】

　　第\(1\)行为\(n\)，表示三角形有\(n\)行。
　　接下来的\(n\)行，第\(i\)行有\(i\)个整数，表示数字三角形中的一个非负整数。

【输出格式】

　　输出最大的和。

【输入输出样例】

　Input

4
1
3 2
4 9 1
4 3 2 20

　Output

24

【数据规模与约定】

　　\(n ≤ 1000\)，数字三角形的每个元素是不超过\(100\)的非负整数。

【来源】

　　Mr.he