C. Штрихкод
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Имеется картинка размера n × m пикселов. Каждый пиксел может быть белым или черным. Требуется изменить цвета как можно меньшего количества пикселов так, чтобы получилась картинка-штрихкод.

Картинка является штрихкодом если выполняются следующие условия:

  • В каждом столбце все пикселы одного цвета.
  • Ширина каждой одноцветной вертикальной полосы не менее x и не более y пикселов. Другими словами, если сгруппировать все соседние столбцы пикселов одного цвета, то не должно получиться группы размера менее x или более y.
Входные данные

В первой строке записаны четыре целых числа через пробел n, m, x и y (1 ≤ n, m, x, y ≤ 1000; x ≤ y).

Далее идет n строк, описывающих исходную картинку. В каждой из этих строк содержится ровно m символов. Символ «.» обозначает белый пиксел, а «#» — черный. Никаких других символов кроме «.» и «#» в описании картинки не содержится.

Выходные данные

В первой строке выведите наименьшее количество пикселов, которое нужно перекрасить. Гарантируется, что ответ существует.

Примеры
Входные данные
6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..
Выходные данные
11
Входные данные
2 5 1 1
#####
.....
Выходные данные
5
Примечание

В первом тестовом примере картинка после перекрашивания может выглядеть следующим образом: 


.##..
.##..
.##..
.##..
.##..
.##..

Во втором тестовом примере картинка после перекрашивания может выглядеть следующим образом: 


.#.#.
.#.#.