C. Trailer Park
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mike recently bought a new trailer and is very excited to use it. However, it is too big to fit in his garage, so he needs to park it in a trailer park. He has found a park, but needs your help figuring out how much it will cost to park his trailer in the park.

The park can be represented as an $$$n \times m$$$ grid, where the $$$j$$$th entry in the $$$i$$$th row costs $$$c_{i,j}$$$ to park in. Some squares will already be occupied, which will be denoted by $$$c_{i,j}=-1$$$.

Mike's trailer can be thought of as an $$$a \times b$$$ rectangle, and he wants to find the cheapest place in the park to park his trailer. Help Mike find how much money he needs to park his trailer, or let him know that the park his no room for his trailer. He can park his trailer in any open $$$a \times b$$$ rectangle in the grid, and costs the sum of $$$c_{i,j}$$$ that he is parked on. Note that the rectangle must be axis-aligned, but it could be rotated by $$$90$$$ degrees.

Input

The first line contains 4 space-seperated integers. The first line contains 4 space-separated integers $$$n$$$, $$$m$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq n,m \leq 2000$$$, $$$1 \leq a \leq n$$$, $$$1 \leq b \leq m$$$) — the number of rows in the grid, columns of the grid, the length of the trailer, and the width of the tralier.

The following $$$n$$$ lines contain $$$m$$$ integers each, describing the trailer park. The $$$j$$$-th element of the $$$i$$$th line $$$a_{i,j}$$$ is -1 if that square foot is taken, and otherwise represents the cost of that square foot, where $$$1 \leq a_{i,j}\leq 10^9$$$.

Output

If it is possible for Mike to park his trailer in the described park, output the minimum cost needed. If it is impossible, output -1.

Examples
Input
3 3 1 2
1 5 -1
7 -1 1
2 3 -1
Output
5
Input
3 3 1 2
-1 5 -1
7 -1 1
-1 3 -1
Output
-1