問題文
dwango 公司拥有一个宽广的庭院。这个庭院南北方向有H行、东西方向有W列,每个区画的尺寸为1米方形。 从北边算起第i行、从西边算起第j列的区画称为区画(i,j)。 庭院里开满了各种花,每个区画都有一个整数表示该区画花的观赏价值。设区画(i,j)的花的观赏价值为 B_{i,j}。
决定至少由一个区块组成的两个矩形,用栅栏将这两个矩形围起来,将未被围起的地方作为道路,从而让庭院变得整洁。这里,两个矩形中包含相同区块是不允许的,但栅栏重叠没有问题。
庭院整体的整洁度,是由任意一个矩形围起来的区块的美观度总和。
为了打造理想的庭园,首先需要求出整洁度的最大值。 请编写一个程序来求庭院整体整洁度的最大值。
入出力
输入是按以下格式从标准输入给出的。
H W
B_{1,1} B_{1,2} … B_{1,W}
:
B_{H,1} B_{H,2} … B_{H,W}
- 1 每行分别表示庭园南北、东西方向的长度。 H, W (2 ≦ H ≦ 300, 2 ≦ W ≦ 300) 用空格分隔。
- 1+i (1 ≦ i ≦ H)每行从北向i第n个区块的美观度表示W个整数 B_{i,1}, ...,B_{i,W} 用空格分隔。
- -10^9≦B_{i,j}≦10^9 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 成立。
配点
针对此问题设置了部分分数。 如果正确答案是满足
- H ≦ 50, W ≦ 50 的数据集 如果正确答案是满足 50 点。
- 如果所有测试用例都正确,则除了上述之外50点。
出力
当确定两个矩形时,庭院整体整洁度的最大值1请按行输出。输出的补充内容也请换行。
入力例1
3 3 1 1 1 1 1 1 1 1 1
出力例1
9
2用几个长方形覆盖整个庭院时,整洁度达到最大9。
入力例2
3 3 -1 -1 -1 -1 -1 -1 -1 -1 -1
出力例2
-2
但有时整洁度残值也可能为负。请注意,长方形必须至少包含一个小区。
入力例3
2 3 5 -1 8 -1 4 -1
出力例3
16
例如,可以像下面这样围起来。
入力例4
4 4 5 2 -3 2 3 8 -3 -10 4 5 3 2 -5 -3 3 5
出力例4
40