#2470. 最大子矩阵和plus

最大子矩阵和plus

题目描述

现在有一个 n×mn\times m 矩阵。要求矩阵中最大子矩阵,但是希蒙又觉得这个问题太简单了,所以他将题目改成了:找一个aabb列的子矩阵,要求此子矩阵的和最大。

输入格式

第一行两个整数n和m,表示矩阵的行和列

第二行两个整数a和b,表示子矩阵的行和列

接下来表示矩阵每个位置的数值t

输出格式

输出a行b列的最大子矩阵之和

样例 #1

样例输入 #1

2 2
1 1
2 0
1 0

样例输出 #1

2

样例 #2

样例输入 #2

4 5
2 2
4 2 1 2 3
3 2 7 5 1
3 4 6 1 2
7 5 9 6 0

样例输出 #2

24

提示

保证 1<=n,m<=30001<= n,m <= 3000 其中 1<=a<=n,1<=b<=m1<=a<=n,1<=b<=m 并且0<=ti<=1000<=t_i<=100