题目描述

有一个包含正数和负数的二维数组。一个子矩阵是指在该二维数组里，任意相邻的下标是 $1\times 1$ 或更大的子数组。一个子矩阵的和是指该子矩阵中所有元素的和。本题中，把具有最大和的子矩阵称为最大子矩阵。

例如：

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$ 行每行输入 $N$ 个整数，表示数组元素。

输出格式

输出最大子阵和。

样例

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

15

数据范围

$1\le N\le 100$，数组元素范围为 $[-127,127]$。

题目来源

CodesOnline