【问题描述】

今天晚上是大毛的生日宴会，大毛妈妈买了一个大蛋糕，分给他和他的朋友们一起吃。这块 蛋糕由 n*(n+1)/2 个格子组成，构成等腰直角三角形的形状，直角边的长度为 n，蛋糕上 每个格子都有自己的“美味值”。如下（n=4）：

1 6 –5 4 
-2 9 3 
0 1 
3 

大毛想将蛋糕沿着格子的边线恰好切成 n 块矩形，且使得其中最难吃的一块蛋糕的“美味值”最大。（一块蛋糕的“美味值”定义为其中每格的“美味值”之和，美味值越大越好吃）

【输入格式】

输入第一行是一个正整数 n。

接下来是第 2~n+1 行，其中第 i 行有(n+2-i)个整数。表示每格的“美味值”

【输出格式】

输出包括一行，为这 n 块蛋糕中最难吃的一块的最大“美味值”（可能是正的、负的或零）。

【样例输入】

4 
1 6 -5 4 
-2 9 3 
0 1 
3

【样例输出】

3 

【数据范围】

对于 50%的数据，1≤n≤100；

对于 100%的数据，1≤n≤300。

所有“美味值”的绝对值≤1,000,000,000。

【样例解释】

如下（同一块蛋糕用同种符号标识）：

#### 
OOX 
OO 
@