11230 - Annoying painting tool

2007/2008 ACM International Collegiate Programming Contest
University of Ulm Local Contest

Problem A: Annoying painting tool

或許你不知道這一個很惱人的繪圖工具。首先 ，它只支援黑白兩種顏色，畫面中只有一個矩形的像素區域。接著只會有一種顏色改變的操作。

選擇一個 r 行(row) x c 列(column) 的區域，接著在內部的所有像素反轉，在這個操作後，原本的黑色會變白色，或者白色轉換成黑色。

一開始所有像素都是白色。創建一張圖，最少要幾次的操作才能繪出心中想的那張圖。

Input Specification

輸入有數筆，每組測資地一行將會有四個整數 n, m, r and c. (1 ≤ r ≤ n ≤ 100, 1 ≤ c ≤ m ≤ 100) 接著會有 n 行，每行上會有 m 個像素。以表示最後要完成的圖形 (以 '0' 表示白色， '1' 表示黑色)。


最後一筆測資將會包含四個 0，結束程序。

Output Specification

對於每組測資輸出最少的操作次數，如果無法轉換，則輸出 "-1" 。

Sample Input

3 3 1 1
010
101
010
4 3 2 1
011
110
011
110
3 4 2 2
0110
0111
0000
0 0 0 0

Sample Output

4
6
-1