Имеется картинка размера n × m пикселов. Каждый пиксел может быть белым или черным. Требуется изменить цвета как можно меньшего количества пикселов так, чтобы получилась картинка-штрихкод.
Картинка является штрихкодом если выполняются следующие условия:
В первой строке записаны четыре целых числа через пробел n, m, x и y (1 ≤ n, m, x, y ≤ 1000; x ≤ y).
Далее идет n строк, описывающих исходную картинку. В каждой из этих строк содержится ровно m символов. Символ «.» обозначает белый пиксел, а «#» — черный. Никаких других символов кроме «.» и «#» в описании картинки не содержится.
В первой строке выведите наименьшее количество пикселов, которое нужно перекрасить. Гарантируется, что ответ существует.
В первом тестовом примере картинка после перекрашивания может выглядеть следующим образом:
.##...##...##...##...##...##..
Во втором тестовом примере картинка после перекрашивания может выглядеть следующим образом:
.#.#..#.#.
6 5 1 2 ##.#. .###. ###.. #...# .##.# ###..
11
2 5 1 1 ##### .....
5
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач