Problems
If You Are Homeless... Just Build a House
If You Are Homeless... Just Build a House
Your Minecraft world looks like a grid $n \times m$, the cell at the intersection of the $i$-th row and the $j$-th column is denoted as $(i, j)$. There are $a_{i, j}$ blocks on the cell $(i, j)$.
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 $1$ 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 $x, y$ 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?
\InputFile
The first line contains two integers $n, m$ ($1 \le n, m \le 500$) --- the size of your Minecraft world.
The second line contains two integers $h, w$ ($1 \le h \le min(n, 20)$, $1 \le w \le min(m, 200)$) --- the dimensions of your future house.
The $i$ th of the next $n$ rows contains $m$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$ ($0 \le a_{i, j} \le 100000$).
\OutputFile
Print a single integer --- the least amount of coins you have to spend to have the necessary area for your house.
\Note
In the first sample, you can increase $a_{1, 1}$ with $1$ coin, obtaining an area of size $1 \times 2$, on each cell of which there are exactly $2$ cubes.
In the second example, you can reduce $a_{2, 1}$ by $2$ with $2$ coins, again obtaining an area of size $1 \times 2$, on each cell of which there are exactly $2$ cubes.
Input example #1
2 3 1 2 1 2 3 4 5 6
Output example #1
1
Input example #2
2 3 1 2 1 6 3 4 2 5
Output example #2
2