Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:128 MB

#112. 最大矩形

Statistics

问题描述:
一个$N * M$的矩阵,每个格子里面有个整数(绝对值不大于10) ,每个子矩阵( 至少包含一个元素 )的价值就是它所包含的格子内的数的和。 现在求两个不相交的子矩阵(不包含相同的格子),使得他们的价值的乘积最大。
例如: N=3 , M=4,矩阵如图所示:
2 3 4 5
1 3 2 4
4 3 2 1
最大子矩阵值乘积为288。(左边两列的和为16,右边两列的和为18,结果为$16*18=288$)。


输入格式:
第一行有两个数字$n, m ( n, m < 100)$。以后的n行,每行有m个整数。


输出格式:
输出文件只有一个数,即两不相交子矩阵价值乘积的最大值。


样例1:
1 7
-9 -9 8 8 1 7 -4
输出:


128