Weather Forecasting

Sunyoung has to forecast the weather for a rectangular region divided into an N x M grid. Each cell contains the time needed to forecast that cell.

She may divide the grid with exactly r horizontal cut lines and exactly s vertical cut lines. These cuts split the grid into (r + 1) x (s + 1) rectangular sections, and all sections can be processed at the same time.

The time needed after the division is therefore the largest sum of cell times among all sections. Find the minimum possible value of that largest section sum.

The first line contains four integers n, m, r, and s (1 <= r < n <= 18, 1 <= s < m <= 18). Here n and m are the grid dimensions, r is the number of horizontal cuts, and s is the number of vertical cuts.

Each of the next n lines contains m integers. The integers are non-negative, and each is at most 2,000,000.

Print the minimum possible time needed to finish the forecasting work.