UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1850. Submatrix

统计 下载数据

Description

很久很久很久以前,有一个古老的主题公园,有一个伟大的工程师QDC,她打算在公园修建一个花坛,花坛周围修建一片绿化带。如果把公园看成一个M*N的矩形,也就是说把公园划分成了M*N块土地,那么绿化带和花坛可以看成一个A*B的矩形,花坛可以看成一个C*D的矩形。如图所示
20 19 18 17 16
15 14 13 12 11
10  9 8  7  6
5  4  3  2  1
QDC经过一段时间的对土地的考察,给每一块土地定了一个“肥沃度”。绿化带的肥沃度定义为A*B-C*D块土地的肥沃度的综合,她希望修建这样的一片绿化带,使得绿化带的肥沃度最大。 花坛一定要完全在绿化带的包围之中,也就是说,A*B的矩阵边上的元素一定不在C*D的举证中。 淡然,这种问题是难不倒QDC的,但是她还有别的更重要的工作要做,于是这个工作就交个你了,薪水很高的哦!

Input

第一行有六个正整数M,N,A,B,C,D。结下来M行,每行有N 个正整数,表示(i,j)的肥沃度。

Output

一个正整数,表示绿化带的最大肥沃程度。

Sample Input

4 5 4 4 2 2
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1

Sample Output

132

Hint

30%的数据, 1<= m , n <= 50 100%的数据, 1<= m , n <= 1000 100%的数据, 1<= A <= M 1 <= B <= n 1 <= C <= A-2 1 <= D <= B-2 1 <= 肥沃度 <= 100

Source