2227: 生日蛋糕
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
今天晚上是大毛的生日宴会，大毛妈妈买了一个大蛋糕，分给他和他的朋友们一起吃。这块
蛋糕由n*(n+1)/2 个格子组成，构成等腰直角三角形的形状，直角边的长度为n，蛋糕上
每个格子都有自己的“美味值”。如下（n=4）：
1 6 -5 4
-2 9 3
0 1
3
大毛想将蛋糕沿着格子的边线恰好切成n 块矩形，且使得其中最难吃的一块蛋糕的“美味
值”最大。（一块蛋糕的“美味值”定义为其中每格的“美味值”之和，美味值越大越好吃）
蛋糕由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)个整数。表示每格的“美味值”。
接下来是第 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
@
对于 50%的数据，1≤n≤100；
对于 100%的数据，1≤n≤300。
所有“美味值”的绝对值≤1,000,000,000。
【样例解释】
如下（同一块蛋糕用同种符号标识）：
####
OOX
OO
@