Grid
Memory limit: 32 MB
The map of Byteland is drawn on a grid of size
( is the vertical dimension, is the horizontal dimension).
The horizontal lines marking the division are called parallels,
and are numbered from to , while the vertical lines of the division
are called meridians, and are numbered from to
(see figure from the example).
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 parallels and meridians into 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
parallels and meridians.
Task
Write a program, that:

reads the dimensions of the map of Byteland, the required number of parallels
and meridians and the unit computation times from the standard input,

finds the minimal time required to compute the complete forecast,

writes the obtained value to the standard output.
Input
The first line of the input contains four integers , , and ,
separated by single spaces (, ).
The following lines contain the computation times of the unit squares.
The th number in the st line is  the time
required to prepare the weather forecast for the unit square located between
the st and th parallel and between the st and th
meridian (, , ).
Additionally, in test cases worth 40% of points, and will not exceed .
Output
Your program should write exactly one line.
It should contain one integer  the optimal computation time.
Example
For the input data:
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
the correct result is:
31
The 2nd and 4th parallel and the 4th 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.
Task author: Zbigniew Czech.