If You Are Homeless... Just Build a House#10824
Your Minecraft world looks like a grid n \times m, the cell at the intersection of the -th row and the -th column is denoted as . There are a_{i, j} blocks on the cell .
With a cost of one coin, you can remove one block from the top of the cell, if there is at least one block there, or add one block on top. In other words, for one coin you can change any a_{i, j} by if it doesn't become negative after.
You want to build a house the size of h \times w. To do this, you need a section of the grid of size h\times w, in which the numbers of blocks in all cells are the same. In other words, to build a house there have to exist some integers with 1 \le x \le n-h+1, 1 \le y \le m-w+1 that all numbers a_{x+i, y+j} for 0\le i < h, 0 \le j < w are equal to each other.
What is the least amount of coins you need to spend to have the necessary area for your new amazing house?
The first line contains two integers (1 \le n, m \le 500) — the size of your Minecraft world.
The second line contains two integers (1 \le h \le min(n, 20), 1 \le w \le min(m, 200)) — the dimensions of your future house.
The th of the next rows contains integers a_{i, 1}, a_{i, 2}, \ldots, a_{i, m} (0 \le a_{i, j} \le 100000).
Print a single integer — the least amount of coins you have to spend to have the necessary area for your house.
Example 1
Example 2
In the first sample, you can increase a_{1, 1} with coin, obtaining an area of size 1 \times 2, on each cell of which there are exactly cubes.
In the second example, you can reduce a_{2, 1} by with coins, again obtaining an area of size 1 \times 2, on each cell of which there are exactly cubes.