Bessie and the Chocolate Chip Brownie Partition

Bessie has baked a rectangular brownie that is represented as an R × C grid (1 ≤ R ≤ 500, 1 ≤ C ≤ 500). Each square at row i, column j contains N_ij chocolate chips (0 ≤ N_ij ≤ 4000).

She wants to partition the brownie into A × B chunks (1 ≤ A ≤ R, 1 ≤ B ≤ C) so that one piece goes to each of the A×B cows. The cutting procedure is as follows:

1. Make A − 1 horizontal cuts (along integer boundaries) to divide the brownie into A contiguous strips.
2. For each horizontal strip, make B − 1 vertical cuts independently (along integer boundaries) to partition the strip into B pieces.

After the partition, the other A×B − 1 cows each pick one piece, leaving Bessie the piece with the minimum number of chocolate chips. Bessie wishes to maximize the number of chocolate chips in the piece that she ends up with.

Formally, if Bessie can guarantee that every one of the A×B pieces has at least X chips, then she will end up with at least X chips. Find the maximum X (expressed in LaTeX below) such that

\( X = \max \{ x : \text{there is a valid partition such that every piece has at least } x \} \).

Example:

Input:
5 4 4 2
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

A possible partition is:

1 2 | 2 1
---------
3   | 1 1 1
---------
2 0 1 | 3
---------
1 1 | 1 1
1 1 | 1 1

When the other greedy cows choose, Bessie gets the piece with 3 chocolate chips.

Assume that Bessie cuts optimally. Your task is to compute the maximum number of chocolate chips Bessie can guarantee for her piece.

inputFormat

The first line contains four integers: R, C, A, and B — the number of rows, columns, horizontal partitions, and vertical partitions respectively.

Each of the next R lines contains C integers, where the j-th integer of the i-th line represents Nij, the number of chocolate chips in that square.

outputFormat

Output a single integer: the maximum number of chocolate chips Bessie can guarantee in her brownie piece.

sample

5 4 4 2
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

3