题目描述

给定一个正整数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

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