题目描述

给定一个 $N \times N$ 的二维数组，数组中包含正数和负数。一个子矩阵是指该二维数组中任意相邻的、大小为 $1 \times 1$ 或更大的子数组。子矩阵的和为该子矩阵中所有元素的和。请找出该数组中和最大的子矩阵，并输出其最大和。

输入格式

第一行：一个正整数 $N$，表示二维方阵的大小。

接下来 $N$ 行：每行包含 $N$ 个整数，表示数组中的元素。

输出格式

输出一个整数，表示最大子矩阵的和。

输入输出样例

输入 #1

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

输出 #1

15

数据规模与约定

• 对于 60% 的数据，$1 \le N \le 100$，数组元素范围为 $[-127, 127]$。
• 对于 100% 的数据，$1 \le N \le 500$，数组元素范围为 $[-127, 127]$。

样例解释

• 选择左上角坐标为(1,2)，右下角坐标为(4,2)的子矩阵，总和为9+2+(-4)+1+(-1)+8=15