CF225C.Barcode

You've got an n × m pixel picture. Each pixel can be white or black. Your task is to change the colors of as few pixels as possible to obtain a barcode picture.

A picture is a barcode if the following conditions are fulfilled:

• All pixels in each column are of the same color.
• The width of each monochrome vertical line is at least x and at most y pixels. In other words, if we group all neighbouring columns of the pixels with equal color, the size of each group can not be less than x or greater than y.

你有一张 $n \times m$ 像素的图片，每个像素为白色或黑色。你的任务是尽可能少地改变像素的颜色，使得最终得到一张条形码图片。

一张图片是条形码图片，当且仅当满足以下条件：

• 每一列中的所有像素颜色相同；
• 每一条单色垂直条带的宽度至少为 $x$、至多为 $y$ 个像素。换言之，若将所有相邻的、颜色相同的列划分为一组，则每组的列数不能少于 $x$，也不能大于 $y$。

The first line contains four space-separated integers n, m, x and y (1 ≤ n, m, x, y ≤ 1000; x ≤ y).

Then follow n lines, describing the original image. Each of these lines contains exactly m characters. Character "." represents a white pixel and "#" represents a black pixel. The picture description doesn't have any other characters besides "." and "#".

第一行包含四个以空格分隔的整数 $n$、$m$、$x$ 和 $y$（$1 ≤ n, m, x, y ≤ 1000$；$x ≤ y$）。

接下来是 $n$ 行，描述原始图像。每行恰好包含 $m$ 个字符。字符 . 表示白色像素，# 表示黑色像素。图像描述中除 . 和 # 外不包含其他字符。

In the first line print the minimum number of pixels to repaint. It is guaranteed that the answer exists.

第一行输出需要重绘的最少像素数量。保证答案存在。

In the first test sample the picture after changing some colors can looks as follows:

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

In the second test sample the picture after changing some colors can looks as follows:

.#.#.
.#.#.

在第一个测试样例中，改变一些颜色后的图案可能如下所示：

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

在第二个测试样例中，改变一些颜色后的图案可能如下所示：

.#.#.
.#.#.