你有一张 n × m 像素的图片。每个像素可以是白色或黑色。你的任务是改变尽可能少的像素的颜色以获得条形码图片。
如果满足以下条件,图片就是条形码:
- 每列中的所有像素都具有相同的颜色。
- 每条单色垂直线的宽度至少为 x 且最多为 y 像素。换句话说,如果我们将具有相同颜色的像素的所有相邻列分组,则每组的大小不能小于x或大于y。
输入
第一行包含四个空格分隔的整数 n、m、x 和 y(1 ≤ n、m、x、y ≤ 1000;x ≤ y)。
然后跟随 n 行,描述原始图像。每行恰好包含 m 个字符。特点 ”。”代表白色像素,“#”代表黑色像素。图片描述中除了“.”之外没有任何其他字符。和 ”#”。
输出
在第一行中打印要重绘的最小像素数。保证答案存在。
示例
输入 #1
6 5 1 2 ##.#. .###. ###.. #...# .##.# ###..
输出 #1
11
输入 #2
2 5 1 1 ##### .....
输出 #2
5
注意
在第一个测试样本中,更改一些颜色后的图片可能如下所示:
.##...##...##...##...##...##..
在第二个测试样本中,更改一些颜色后的图片可能如下所示:
.#.#..#.#.