分数: 400 分
问题陈述
高桥有一个网格 N 行和 M 列。所在行的单元格 i 和专栏 网格的 j 包含一个整数 A_{i,j}.
Takahashi 将从该网格中选择一个矩形区域,并计算该区域中包含的所有单元格的值的总和。这里,“矩形区域”是指由行之间的所有单元格组成的区域 r_1 和 r_2 (含)且其列位于 c_1 和 c_2 (含),其中 r_1, r_2 (1 \le r_1 \le r_2 \le N)和 c_1, c_2 (1 \le c_1 \le c_2 \le M) 是选定的整数。
Takahashi 希望选择矩形区域以使该总和最大化。请注意,矩形区域必须至少包含一个单元格,因此不可能选择没有矩形区域且总和为 0。特别是,即使所有单元格值为负,他仍然必须选择一些矩形区域。
找出高桥可以选择的矩形区域内的最大可能值之和。
约束
- 1 \leq N \leq 500
- 1 \leq M \leq 500
- -10^4 \leq A_{i,j} \leq 10^4
- 所有输入值均为整数
输入
N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
- 第一行包含一个整数 N 表示行数和一个整数 M 表示网格的列数,以空格分隔。
- 以下 N 行每条描述网格的一行。的 i- 这些行(1 \le i \le N) 包含值 行中单元格的 A_{i,1}, A_{i,2}, \ldots, A_{i,M} 网格的 i ,用空格分隔。
输出
在高桥可以选择的矩形区域内打印最大可能的值之和,作为单行的整数。
样本输入 1
3 3 1 -2 3 -4 5 6 7 -8 9
示例输出 1
18
示例输入 2
2 2 -5 -3 -1 -7
示例输出 2
-1
示例输入 3
5 4 2 1 -3 4 -1 3 2 -1 4 -2 1 3 -3 1 -4 2 1 2 3 -1
示例输出 3
14
示例输入 4
8 10 3 -1 2 -4 5 1 -3 2 4 -2 -2 4 1 3 -1 2 -5 3 1 0 1 -3 5 2 4 -1 3 -2 1 2 -4 2 -1 6 3 5 -2 4 -3 1 0 1 3 -2 4 2 1 -1 5 3 -1 -2 4 1 -3 6 2 3 -4 2 3 1 -5 2 1 -2 4 1 3 -1 -2 3 2 -1 3 1 -3 2 -1 4
示例输出 4
77
示例输入 5
1 1 -7
示例输出 5
-7