题目描述

在遥远的未来，星际矿业公司“天穹”派遣了一支精英团队前往一颗新发现的资源星球“艾瑞斯”。这颗星球蕴藏着丰富的稀有矿物，但分布极不均匀，有的区域富得流油，有的区域却寸草不生。

团队的任务是利用先进的扫描技术，绘制出一张 n \times n 的矿藏价值矩阵。矩阵中的每个元素代表着对应区域的矿物价值，正数表示收益，负数表示开采成本（例如，需要移除的岩石或有害物质）。

然而，公司的规定十分苛刻：只能选择一个矩形区域进行开采，而且必须保证开采的总收益最大化。如果开采的总收益为负，那么这次任务就算失败，整个团队将面临降薪甚至解雇的风险。

团队的首席工程师艾米，是一位经验丰富的算法专家。

“矩阵中的每个元素都是一个整数，范围在 [-127, 127] 之间。矩形的大小没有限制，但我们必须找到那个包含的所有元素之和最大的矩形，才能确保这次任务的成功！”艾米对着团队成员说道。

请帮助他们完成任务。

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

最大矩形在左下角：

9  2
-4  1
-1  8

和为 15。

第一行：n，接下来是 n 行 n 列的矩阵。

最大矩形（子矩阵）的和。

1 \leq n\le 120

前缀和