In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
Write a program, that:
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 .
Your program should write exactly one line. It should contain one integer - the optimal computation time.
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:
The 2-nd and 4-th parallel and the 4-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.
Task author: Zbigniew Czech.