UOJ Logo

NOI.AC

1S 512MB

#1299. 最大子矩阵和

Statistics

给一个$n \times m$的矩阵,求最大子矩阵和。

数据输入

第一行两个数字:$n$和$m$,分别表示矩阵的行数和列数。

接下来$n$行,每行$m$个数字,代表矩阵的元素值。

数据输出

一个数字,表示最大子矩阵和。

样例输入1

2 2

1 2

3 4

样例输出1

10

样例输入2

3 3

1 2 -3

-3 3 4

4 3 -10

样例输出2

10

范围说明

对于$100%$的数据:$1 \leq n, m \leq 80$,矩阵中元素的绝对值$\leq 10^9$。