Reservoir Dogs
– Who goes there? – asked Fao (in the jungle, this question is always asked after the sound of a trumpet). – Dholes, dholes, the Deccan dholes! The red killer dogs! They come from the south, saying there is no game in the Deccan.
Before entering the Seeonee valley, the pack of hungry red dogs arranged themselves in a rectangular battle formation of NxM dogs. With wild barking and terrible howling, they greeted their leader. However, the leader was not impressed by such a cacophony; he had his own ideas on how he should be greeted.
Using his authority, he can issue a command any number of times to make the dogs in any subrectangle of the battle formation of size KxL (where the vertical side length is K and the horizontal side length is L) switch from howling to barking, and from barking to howling.
Is it possible for him to achieve a harmonious greeting from his pack?
Input
The first line of the input file contains the numbers N, M, K, L (1 ≤ N, M, K, L ≤ 100, K ≤ N, L ≤ M).
In the next N lines, there are M numbers, where 1 means the dog is barking, and 0 means the dog is howling. These N lines represent the initial cacophony. In the following N lines, the desired harmonious greeting is recorded in the same format.
Output
The output file should contain the smallest number of commands the leader needs to give to achieve the harmonious greeting, or -1 if such a set of commands does not exist.