Имеется картинка размера n × m пикселов. Каждый пиксел может быть белым или черным. Требуется изменить цвета как можно меньшего количества пикселов так, чтобы получилась картинка-штрихкод.
Картинка является штрихкодом если выполняются следующие условия:
- В каждом столбце все пикселы одного цвета.
- Ширина каждой одноцветной вертикальной полосы не менее x и не более y пикселов. Другими словами, если сгруппировать все соседние столбцы пикселов одного цвета, то не должно получиться группы размера менее x или более y.
Выходные данные
В первой строке выведите наименьшее количество пикселов, которое нужно перекрасить. Гарантируется, что ответ существует.
Примечание
В первом тестовом примере картинка после перекрашивания может выглядеть следующим образом:
.##..
.##..
.##..
.##..
.##..
.##..
Во втором тестовом примере картинка после перекрашивания может выглядеть следующим образом:
.#.#.
.#.#.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..
|
11
|
|
2
|
2 5 1 1
#####
.....
|
5
|