Barcode

题意翻译

给出一个 $n×m$ 的矩阵，初始时有颜色，$\verb!.!$ 表示白色，$\verb!#!$ 表示黑色，要求修改最少位置的颜色使得满足以下两个条件： 1. 每列颜色相同； 1. 连续相同颜色的列数介于 $[x,y]$ 之间。

题目描述

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 $ .

输入输出格式

输入格式

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 "\#".

输出格式

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

输入输出样例

输入样例 #1

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

输出样例 #1

11

输入样例 #2

2 5 1 1
#####
.....

输出样例 #2

5

说明

In the first test sample the picture after changing some colors can looks as follows: `<br></br>.##..<br></br>.##..<br></br>.##..<br></br>.##..<br></br>.##..<br></br>.##..<br></br>`In the second test sample the picture after changing some colors can looks as follows: `<br></br>.#.#.<br></br>.#.#.<br></br>`