Optimal Partitioning of Byteland’s Weather Grid

Byteland’s map is represented as an $n \times m$ grid, where $n$ is the vertical (row) count and $m$ is the horizontal (column) count. The grid is demarcated by horizontal lines (called parallels) numbered from $0$ to $n$ and vertical lines (called meridians) numbered from $0$ to $m$. Each cell in the grid requires a given amount of processing time when computing the weather forecast.

Initially the forecast system processes each cell sequentially; hence the total processing time is the sum over all cells. In the new multi-processor system, Byteland is to be partitioned by selecting exactly $r$ parallels and $s$ meridians to divide the grid into $(r+1)(s+1)$ rectangular regions. Each processor thread will handle one rectangular region and will require a processing time equal to the sum of all the cells within that region. The overall processing time for completing the forecast is determined by the region that takes the maximum time.

Your task is to choose the $r$ horizontal lines and $s$ vertical lines such that the maximum processing time among all resulting rectangles is minimized. Formally, if you partition the grid into regions using $r$ horizontal cuts and $s$ vertical cuts, let each region’s sum be defined as the sum of all cell processing times within that region. You want to minimize the value $$T = \max_{\text{rectangle}} \text{(region sum)}.$$

You are given the grid dimensions $n$ and $m$, the numbers $r$ and $s$, and the processing time for each cell. Output the minimum possible $T$ so that there exists a partition (by selecting exactly $r$ horizontal lines and $s$ vertical lines) guaranteeing that every rectangle’s processing time is at most $T$.

## inputFormat

The first line contains four integers $n$, $m$, $r$, and $s$, where $1\leq n,m\leq 10$ (assumed small for brute-force vertical partitioning) and $0\le r < n$, $0\le s < m$. The next $n$ lines each contain $m$ integers, where the $j$-th integer on the $i$-th line represents the processing time of the cell in row $i$ and column $j$. It is guaranteed that all processing times are positive integers.

## outputFormat

Output a single integer --- the minimum possible maximum processing time among all rectangles when the grid is partitioned optimally using $r$ horizontal cuts and $s$ vertical cuts.

## sample

3 3 1 1
1 2 3
4 5 6
7 8 9

15

$$