Раздражающий инструмент для рисования
Вам наверное интересно, какой инструмент для рисования картин является наиболее раздражающим? Во-первых инструмент, про который мы говорим, рисует только черным и белым. То есть картина представляет собой прямоугольную область, состоящую только из черных и белых точек. Во-вторых, существует только одна операция, позволяющая изменять цвет точек:
Выделите прямоугольную область, состоящую из r строк и c столбцов, находящуюся полностью внутри картины. В результате операции каждая точка внутри выбранного прямоугольника изменяет свой цвет на противоположный (черный на белый, а белый на черный).
Изначально все точки имеют белый цвет. Для создания картины описанные выше действия могут применяться несколько раз. Необходимо определить, сможете ли вы нарисовать заданную картину.
Входные данные
Состоит из нескольких тестов. Первая строка каждого теста содержит четыре целых числа n, m, r и c (1 ≤ r ≤ n ≤ 100, 1 ≤ c ≤ m ≤ 100). Следующие n строк описывают картину, которую Вы хотите нарисовать. i-ая входная строка состоит из m символов, задающих цвет точек в i-ой строке законченной картины ('0' указывает на белый цвет, '1' указывает на черный).
За последним тестом следует строка, содержащая четыре нуля.
Выходные данные
Для каждого теста выведите в отдельной строке наименьшее количество операций, необходимое для создания картины, или -1 если создать картину невозможно.