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 "#".
import pdb

def solve(n, m, x, y, barcode):
    dp = [[(float('inf'), float('inf')) for _ in range(2)] for _ in range(m)]
    s = sum(barcode[:x])
    dp[x-1][0] = (s, x)
    dp[x-1][1] = (n*x - s, x)
    for i in range(x, m):
        r = i + 1
        mnw = (float('inf'), float('inf'))
        mnb = (float('inf'), float('inf'))
        for j in range(y):
            used_cells = j + 1
            white_val = sum(barcode[i-j: r])
            white_cols = dp[i - j - 1][0][1] + used_cells
            if x <= white_cols and white_cols <= y:
                aux = white_val + dp[i - j - 1][0][0]
                if aux < mnw[0]:
                    mnw = (aux, white_cols)
            if x <= used_cells and used_cells <= y:
                aux = white_val + dp[i - j - 1][1][0]
                if aux < mnw[0]:
                    mnw = (aux, used_cells)
            black_val = n*used_cells - white_val
            black_cols = dp[i - j - 1][1][1] + used_cells
            if x <= black_cols and  black_cols <= y:
                aux = black_val + dp[i - j - 1][1][0]
                if aux < mnb[0]:
                    mnb = (aux, black_cols)
            if x <= used_cells and used_cells <= y:
                aux = black_val + dp[i - j - 1][0][0]
                if aux < mnb[0]:
                    mnb = (aux, used_cells)
        dp[i][0] = mnw
        dp[i][1] = mnb
    return min(dp[m-1][0][0], dp[m-1][1][0])

def main():
    n, m, x, y = map(int, input().split())
    barcode = [0]*m
    for _ in range(n):
        line = input()
        for i, ch in enumerate(line):
            if ch == '#':
                barcode[i] += 1
    sol = solve(n, m, x, y, barcode)
    print(sol)

if __name__ == '__main__':
    main()
