2231: 生日蛋糕II

小毛是大毛的双胞胎弟弟。但大毛出生时是 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