Description
You've got an n × m
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.
Input
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 "#".
Output
In the first line print the minimum number of pixels to repaint. It is guaranteed that the answer exists.
Sample Input
Input
6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..
Output
11
Input
2 5 1 1
#####
.....
Output
5
Hint
In the first test sample the picture after changing some colors can looks as follows:
.##..
.##..
.##..
.##..
.##..
.##..
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 2005;
int f[maxn][2];
int x, y, n, m, i, j, a[maxn],b[maxn];
char s[maxn];
int main(){
while (cin >> n >> m >> x >> y)
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(f, 1, sizeof(f));
for (i = 1; i <= n; i++)
{
scanf("%s", s);
for (j = 0; j < m;j++)
if (s[j] == '#') a[j + 1]++; else b[j + 1]++;
}
for (j = 1; j <= m; j++) a[j + 1] += a[j], b[j + 1] += b[j];
f[0][0] = f[0][1] = 0;
for (i = 0; i < m; i++)
{
for (j = x; j <= y; j++)
{
f[i + j][0] = min(f[i + j][0], f[i][1] + a[i + j] - a[i]);
f[i + j][1] = min(f[i + j][1], f[i][0] + b[i + j] - b[i]);
}
}
cout << min(f[m][0], f[m][1]) << endl;
}
return 0;
}