【问题描述】

小毛是大毛的双胞胎弟弟。但大毛出生时是 23:59，小毛小他 1 分钟，无奈只好分两天过生日。不过分两天过生日也有一个好处，就是可以吃到两块生日蛋糕。

听说昨天的三角形蛋糕切得比较痛苦，小毛妈妈（也就是大毛妈妈）今天买了一块正方形蛋糕（为什么不是圆形的？！）。蛋糕是正方形格子组成的 n 阶方阵，每格都有自己的“美味值”（美味值为一正整数）。

小毛想将蛋糕沿着格子的边线恰好切成 n 块，且使得其中最难吃的一块蛋糕的“美味值”最大。（一块蛋糕的“美味值”定义为其中每格的“美味值”之和，美味值越大越好吃）每块蛋糕的形状没有限制，但必须是不裂开的（组成这块蛋糕的各个格子需要以边相连的方式成为一个连通块；角相连不算连通）。

【输入格式】

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

接下来的 n 行，每行 n 个正整数，表示每格的美味值。

【输出】

输出包括一行，为这 n 块蛋糕中最难吃的一块的最大“美味值”。

【样例输入】

4 
1 1 1 1 
1 3 9 1 
1 12 12 1 
1 1 1 1 

【样例输出】

12

【样例解释】

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

#### 
#XX# 
#O@# 
#### 

【数据范围】

对于 30%的数据，1≤n≤3；

对于 60%的数据，1≤n≤10；

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

0<“美味值”<1000