题目描述

给定一个 $N \times N$ 的整数矩阵。一个非空子矩阵的大小定义为其中所有元素之和。

请在原矩阵中选择一个连续的矩形区域，使该区域内所有元素之和最大，并输出这个最大值。

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含 $N$ 个整数，第 $i$ 行第 $j$ 个整数表示矩阵元素 $a_{i,j}$。

输出格式

输出一行一个整数，表示非空子矩阵的最大元素和。

样例

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

15

数据范围与提示

• $1 \le N \le 100$
• $-127 \le a_{i,j} \le 127$