Annoying Painting Tool

Interview

Time limit1sMemory limit128 MB

Summary

Given a target black-and-white grid and a fixed r by c flip rectangle, find the minimum number of flips to reach it, or report impossibility.

Level: Medium6 of 10
Topics: Greedy, Simulation, Implementation, Prefix sum
Solved: No attempts yet

Problem

Maybe you wonder what an annoying painting tool is? First of all, the painting tool we speak of supports only black and white. Therefore, a picture consists of a rectangular area of pixels, which are either black or white. Second, there is only one operation to change the colour of pixels.

Select a rectangular area of $r$ rows and $c$ columns of pixels, which lies completely inside the picture. As a result of the operation, every pixel inside the selected rectangle changes its colour (from black to white, or from white to black).

Initially, all pixels are white. To create a picture, the operation described above can be applied several times. Can you paint a certain picture you have in mind?

Input

The input contains several test cases. Each test case starts with one line containing four integers $n$ , $m$ , $r$ , and $c$ ( $1 \le r \le n \le 100$ , $1 \le c \le m \le 100$ ). The following $n$ lines each describe one row of pixels of the painting you want to create. The $i$ -th line consists of $m$ characters describing the desired pixel values of the $i$ -th row in the finished painting ('0' indicates white, '1' indicates black).

The last test case is followed by a line containing four zeros.

Output

For each test case, print the minimum number of operations needed to create the painting, or $-1$ if it is impossible.

Examples3

Example 1

Input

Expected output

4
6
-1

Example 2
Input
```
2 2 1 1
00
00
0 0 0 0
```
Expected output
```
0
```
Example 3
Input
```
1 1 1 1
1
0 0 0 0
```
Expected output
```
1
```