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 main():
    n, m, x, y = list(map(int, input().split()))
    Grid = []
    Hash_count = [0 for _ in range(m)]
    for i in range(n):
        Grid.append(input())
        for i in range(m):
            if Grid[-1][i] == '#':
                Hash_count[i] += 1
    cols = [(n - Hash_count[i], Hash_count[i]) for i in range(m)] # no of dot to change to H, no of H to change to dot
    infinity = float('inf')
    X = [[0, 0, 0, 0, 0] for _ in range(m)]
    X[0] = [cols[0][0], infinity, cols[0][1], infinity, min(cols[0][1], cols[0][0])]
    
    for i in range(1, m):
        if ((i + 1) % (y) != 0):
            X[i][0] = X[i - 1][0] + cols[i][0]
            X[i][2] = X[i - 1][2] + cols[i][1]
        else:
            X[i][0] = infinity
            X[i][2] = infinity
            X[i][1] = min(X[i - 1][2], X[i - 1][3]) + cols[i][0]
            X[i][3] = min(X[i - 1][0], X[i - 1][1]) + cols[i][1]
            X[i][4] = min(X[i][0], X[i][1], X[i][2], X[i][3])
            X[i] = [X[i][4], infinity, X[i][4], infinity, X[i][4]]
            continue
        if (i % x == 0):
            X[i][1] = X[i - 1][2] + cols[i][0]
            X[i][3] = X[i - 1][0] + cols[i][1]
        else:
            X[i][1] = infinity
            X[i][2] = infinity
        X[i][4] = min(X[i][0], X[i][1], X[i][2], X[i][3])
    print(X[-1][4])



if __name__ == "__main__":
    main()