提示: 欢迎访问OurACM平台。
Problem 1520 Graph Transformation

Accept: 176    Submit: 271
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Given a graph composed of n * m grids , the color of each grid is either black or white. Every step of gragh transform operation can transform a subgraph B which is size of r * c within graph A,and let all the grids in graph B turn into its opposite color. Please design of an algorithm to calculate the minimal number of steps can transform graph A into an all white graph.

Input

There are multiple test cases. The first line of each test case contains four positive integers n,m,r,c. (1 ≤ r ≤ n ≤ 100, 1 ≤ c ≤ m ≤ 100). indicating that graph A has n rows ,m columns and subgraph B has r rows,c columns. In the following n lines, each line contains a m-length 01string, indicating the graph A,0 for white and 1 for black.

Output

For each test case, print a line containing an integer which indicting the minimal transform steps, if it is impossible to transform,please output " No solution!".

Sample Input

3 4 1 1 0110 0111 0000 4 8 1 7 10000001 10000001 10000001 11111110 2 8 1 4 10010111 01010101

Sample Output

5 7 No solution!

Source

FZU 2007 ICPC Qualification Round I

Submit  Back  Status  Discuss