Coverage

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).

**Input**

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].

**Output**

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**

6

Author:

**ZHUANG, Junyuan**
Source:

**ZOJ Monthly, July 2009**
Submit
Status