2924 - 【入门】最大子阵

通过次数

7

提交次数

16

时间限制 : 1 秒
内存限制 : 128 MB

给定一个 n \times m 的矩阵 A,求 A 中的一个非空子矩阵,使这个子矩阵中的元素和最大。

输入

输入的第一行包含两个整数 n,m(1 \leq n,m \leq 50),分别表示矩阵 A 的行数和列数。接下来 n 行,每行 m 个整数,表示矩阵 A_{i,j}(-1000 \leq A_{i,j} \leq 1000)

输出

输出一行,包含一个整数,表示 A 中最大的子矩阵中的元素和。

样例

输入

3 3
2 -4 1
-1 2 1
4 -2 2

输出

6

提示

枚举子矩阵的行数在 x_1x_2 之间,列数在 y_1y_2 之间,然后统计其中的和,更新当前最大值。