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

The first line contains four space-separated integers $ n $ , $ m $ , $ x $ and $ y $ ( $ 1

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: `

.#.#.

.#.#.

`