题目描述

给定一个正整数n（ n<=500），然后输入一个N $\times$ N矩阵。求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，使其中包含的所有元素的和最大 。矩阵的每个元素属于[-1100,1100]

例：

0–2 –7  0　　　　　　 在左下角：   9  2

  

9  2 –6  2　　　　　　　　　　　　  -4  1　　 

  

-4  1 –4  1　　　　　　　　　　    -1  8  



-1  8  0 –2　　　　　　　　　　   和为15

输入格式

第一行：n，

接下来是n行n列的矩阵。

输出格式

一个整数，表示最大子矩阵的和。

样例数据

input

4

0 -2 -7 0

9 2 -6 2

-4 1 -4  1 

-1 8  0 -2

output

15

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$

注释 Hint

经典问题，考虑如何降维。