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 "#".
def solve(liste, x, minimum, limit):
    s = [(0, liste[0], 1),(0, x-liste[0], 1)]
    min = float('inf')
    while len(s) > 0:
        i, curr, length = s.pop()
        if length < limit and i < len(liste) - 1 and curr + liste[i + 1] < min:
            s.append((i + 1, curr + liste[i + 1], length + 1))
        if length >= minimum and i < len(liste) - 1 and curr + x - liste[i + 1] < min:
            s.append((i + 1, curr + x - liste[i + 1], 1))
        if i == len(liste) - 1 and curr < min:
            min = curr
    return min

x, y, minimum, limit = list(map(lambda x: int(x), input().split()))
matrix = [[i for i in input()] for _ in range(x)]
whites = [0]*y
for lign in matrix:
    for i in range(y):
        if lign[i] == ".":
            whites[i] += 1

print(solve(whites, x, minimum, limit))
