Brownie Slicing

Bessie has baked a rectangular brownie that can be viewed as an $R \times C$ grid ($1 \le R \le 500$, $1 \le C \le 500$) of little brownie squares. The square at row $i$, column $j$ contains $N_{ij}$ chocolate chips ($0 \le N_{ij} \le 4000$).

Bessie wants to partition the brownie into $A \times B$ chunks ($1 \le A \le R$, $1 \le B \le C$): one for each of the $A \times B$ cows. She cuts the brownie by first making $A-1$ horizontal cuts (always along integer coordinates) to divide it into $A$ strips. Then she cuts each strip independently with $B-1$ vertical cuts, also on integer boundaries, so every strip becomes $B$ pieces. This yields $A \times B$ pieces in total.

Afterwards, $A \times B - 1$ of the cows each pick a piece, leaving the last piece for Bessie. Because the cows are greedy, they leave Bessie the piece with the fewest chocolate chips.

Determine the maximum number of chocolate chips Bessie can guarantee for herself, assuming she cuts optimally.

For example, consider a $5 \times 4$ brownie with chips distributed as follows:

1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

Here $A = 4$ and $B = 2$, so Bessie must cut the brownie into 4 horizontal strips, each split into two pieces. She can cut it like this:

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

Now every piece holds at least 3 chocolate chips, so even after the greedy cows take theirs, Bessie is left with 3.

• Line 1: four space-separated integers $R$, $C$, $A$, and $B$.
• Lines 2 to $R+1$: line $i+1$ contains $C$ space-separated integers $N_{i1}, \ldots, N_{iC}$.

• Line 1: a single integer — the maximum number of chocolate chips Bessie can guarantee for her piece.