锁定富矿

坑道的三维结构图在你们面前展开——不是普通地图，是一张能量密度热力图。颜色越深的地方，矿物储量越高。Echo说Zero的仓库总是建在富矿带上，因为矿物可以为服务器提供能源。

"要找到最大的富矿区。"你说，"在一片区域里找一块子区域，让它的总能量最高。"

"就像……"CC想了想，"在一片田里找最肥的一块地？"

"对。"

你开始写。先固定子区域的上下边界——上边界从第1行开始，下边界从上边界开始往下扩。每确定一对上下边界，就把这两行之间的所有元素按列求和，压缩成一条一维的矿脉。然后在这条矿脉里找最肥的连续段——从左到右扫描，累加当前段的能量，如果累加变成负数了就重新开张。

屏幕上跳出了结果。最大子区域对应的坐标——坑道东侧，第三层到第五层，第12列到第18列。

"仓库在那里。"Echo说。

CC把热力图放大到那个区域。确实——一个半掩在岩壁里的金属结构，门口有两个Zero的守卫在巡逻。

"只有两个。"CC说，"我能解决。"

"等等。"你说，"我们还需要补给。老周和陈叔被关了多久？"

"三天。"Echo说。

"那需要食物和水。"你说，"而且我们六个人——你、我、CC、Echo、老周、陈叔——物资要均分。"

题目描述

$n \times m$ 的矩阵，每个元素代表能量密度。求一个子矩阵，使其元素和最大。

输入格式

$n, m$。然后 $n \times m$ 的矩阵。

输出格式

最大子矩阵和。

输入样例

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

输出样例

15

提示

• 枚举上下边界，压缩成一维数组。
• 在一维数组上求最大子段和。
• 最大子段和：从左到右扫描，维护当前累加和，变负则重置。

仓库里的补给比想象中多——六箱压缩食品，八瓶过滤水，还有一些医疗包。但你们现在有六个人：你、CC、Echo、老周、陈叔，还有 Echo 的投影虽然没有实体，但她的终端需要能源。

"每人该分多少？"CC把物资堆在地板上，金属手臂在搬重物时发出轻微的摩擦声。

"先算平均值。"你说，"总物资除以六，得到每人该得的数量。然后看每个人现在手里有多少，多了的给少了的。"

"环形坐。"老周忽然开口——这是他获救后说的第一句话，声音沙哑得像砂纸摩擦，"我们围成一圈，每次只能给相邻的人。这样最安全——Zero 的监控不会注意到小量的传递。"