Задачи
Раздражающий инструмент для рисования
Раздражающий инструмент для рисования
Вам наверное интересно, какой инструмент для рисования картин является наиболее раздражающим? Во-первых инструмент, про который мы говорим, рисует только черным и белым. То есть картина представляет собой прямоугольную область, состоящую только из черных и белых точек. Во-вторых, существует только одна операция, позволяющая изменять цвет точек:
Выделите прямоугольную область, состоящую из \textbf{r} строк и \textbf{c} столбцов, находящуюся полностью внутри картины. В результате операции каждая точка внутри выбранного прямоугольника изменяет свой цвет на противоположный (черный на белый, а белый на черный).
Изначально все точки имеют белый цвет. Для создания картины описанные выше действия могут применяться несколько раз. Необходимо определить, сможете ли вы нарисовать заданную картину.
\InputFile
Состоит из нескольких тестов. Первая строка каждого теста содержит четыре целых числа \textbf{n}, \textbf{m}, \textbf{r} и \textbf{c} (\textbf{1} ≤ \textbf{r} ≤ \textbf{n} ≤ \textbf{100}, \textbf{1} ≤ \textbf{c} ≤ \textbf{m} ≤ \textbf{100}). Следующие \textbf{n} строк описывают картину, которую Вы хотите нарисовать. \textbf{i}-ая входная строка состоит из \textbf{m} символов, задающих цвет точек в \textbf{i}-ой строке законченной картины ('\textbf{0}' указывает на белый цвет, '\textbf{1}' указывает на черный).
За последним тестом следует строка, содержащая четыре нуля.
\OutputFile
Для каждого теста выведите в отдельной строке наименьшее количество операций, необходимое для создания картины, или -\textbf{1} если создать картину невозможно.
Входные данные #1
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
Выходные данные #1
4 6 -1