Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3222

Time Limit: 2 Seconds      Memory Limit: 32768 KB

Consider the following situation. Each grid point in an infinite two-dimention plane is assigned an integer value. All values except a very special group of points lying in a matrix of N * M are ZERO. The values in the matrix will be given.

Now you have a board of rectangle of size H * W. Cut the board into two rectangles. Assume that their sizes are a1 * b1 and a2 * b2 (These four numbers should all be positive integers). We can use them to cover a matrix of a1 * b1 and a matrix of a2 * b2. You are to maximize the sum of all the values in the two matrices.

Note: The board CANNOT rotate but the two matrices can overlap(Values in both matrices are counted twice).


There are no more than 30 cases. Proceed till the end of file.
The first line of each case is four integers N, M, H, W (2 <= H <= N <= 100, 2 <= W <= M <= 100).
Then follows N lines each of M integers indicating the values in the special matrix. Integers are in range [-10000, 10000].


For each case print the max sum.

Sample Input

3 4 3 2
-1 1 -1 -1
-1 1 -1 -1
-1 1 -1 -1

Sample Output


Author: ZHUANG, Junyuan
Source: ZOJ Monthly, July 2009
Submit    Status