题目描述

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空（大小至少为 $1\times1$）子矩阵。

例如，下列 $4\times4$ 矩阵：

0  -2  -7   0
9   2  -6   2
-4  1  -4   1
-1  8   0  -2

它的最大子矩阵是：

9   2
-4  1
-1  8

这个子矩阵的大小（即元素和）是 $15$。

输入格式

• 输入的第一行包含一个整数 $N$，表示矩阵为 $N\times N$，其中 $0 < N \leq 100$。
• 接下来给出 $N^2$ 个整数，按行顺序给出矩阵中的元素（先从左到右给出第一行的 $N$ 个整数，再从左到右给出第二行的 $N$ 个整数，依此类推）。
• 整数之间由空格或换行分隔。
• 保证矩阵中整数的范围为 $[-127, 127]$。

输出格式

对于每组测试数据，输出一个整数，表示矩阵的最大子矩阵大小。

样例

1
27 
3
-40 29 -16 
38 18 22 
24 -35 5 

27
78