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

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.