Baltic Olympiad in Informatics: 2008 Day 2, Problem 2

The map of Byteland is drawn on a grid with height $n$ and width $m$. The horizontal lines marking the division are called parallels, and are numbered from $0$ to $n$, while the vertical lines of the division are called meridians, and are numbered from $0$ to $m$.

Weather forecasting is a serious issue in Byteland. For each unit square of the grid a certain amount of computation time is required to prepare the forecast. Due to terrain conditions and other factors this time may vary from square to square. Until very recently the forecasting system was processing the unit squares one after another, so it took as long as the sum of all the unit times to prepare the complete forecast.

You have been asked to design a new system, running on a multiprocessor computer. To share the computations among processors, the area of Byteland should be divided by $r$ parallels and $s$ meridians into $(r+1)(s+1)$ smaller rectangles. Each processor will cover one rectangle of this division and will process the squares of this rectangle one after another. This way the computation time for such rectangle will be the sum of all computation times of the unit squares contained in this rectangle. The computation time of the complete forecast will be the maximum among computation times of the individual processors.

Your task is to find the minimal possible computation time for some choice of $r$ parallels and $s$ meridians.

Constraints

$1\le r<n\le 18$

$1\le s<m\le 18$

$0\le c_{i,j}\le 2\times {10}^6$

Subtask 1 [40%]

$1\le n,m\le 10$

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line of the input contains four, space-separated integers $n$, $m$, $r$ and $s$. The following $n$ lines contain the computation times of the unit squares. The $j^{\text{th}}$ number in the $(i+1{)}^{\text{st}}$ line is $c_{i,j}$ — the time required to prepare the weather forecast for the unit square located between the $(i-1{)}^{\text{st}}$ and $i^{\text{th}}$ parallel and between the $(j-1{)}^{\text{st}}$ and $j^{\text{th}}$ meridian $(1\le i\le n,1\le j\le m)$.

Output Specification

Output exactly one line, containing the optimal computation time.

Sample Input

7 8 2 1
0 0 2 6 1 1 0 0
1 4 4 4 4 4 3 0
2 4 4 4 4 4 3 0
1 4 4 4 8 4 4 0
0 3 4 4 4 4 4 3
0 1 1 3 4 4 3 0
0 0 0 1 2 1 2 0

Sample Output

31

Explanation

The $2^{\text{nd}}$ and $4^{\text{th}}$ parallel, along with the $4^{\text{th}}$ meridian, divide the country into $6$ rectangles with computation times $21,13,27,27,17,31$. The computation time of the complete forecast is $31$.