400100 - 数字三角形
一个数字构成的三角形：第i行有i个数字，上层数字与左下和右下的数字之间构成路径，求从顶点到底边的全部路径中经过数字之和最大。
Input
第一行，一个数字n，表示行数。
接下来n行，每行n个非负数a_{yx}。
对于100%的数据：
1\le n \le 100；
0\le a_{yx} \le 100。
Output
一行，一个数字，表示最大和。
Examples
Input
5 11 11 8 12 3 26 6 12 15 8 27 7 13 24 11
Output
84