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 sys
from typing import Callable


def rec(n, count_b, count_w, x, y,  col, width_b, width_w, memo) -> int:
    if col >= n:
        # If we reached the end and the current width is invalid
        if 0 < width_b < x or 0 < width_w < x:
            return float('inf')
        return 0
    k = (col, width_b, width_w)
    if k in memo:
        return memo[k]
    cost_removing_b = count_b[col]
    cost_removing_w = count_w[col]
    if width_b >= y:
        # Can only do white
        val =  rec(n, count_b, count_w, x, y, col + 1, 0, width_w + 1, memo) + cost_removing_w
    elif width_w >= y:
        # Can only do black
        val =  rec(n, count_b, count_w, x, y, col + 1, width_b + 1, 0, memo) + cost_removing_b
    else:
        removing_w = cost_removing_w + rec(n, count_b, count_w, x, y, col + 1, 0, width_w + 1, memo)
        removing_b = cost_removing_b + rec(n, count_b, count_w, x, y, col + 1, width_b + 1, 0, memo)
        val = min(removing_w, removing_b)
    memo[k] = val
    return val

def main() -> None:
    read: Callable[[], str] = sys.stdin.readline
    m, n, x, y = (int(i) for i in read().split())
    count_b = [0] * n
    count_w = [0] * n
    for _ in range(m):
        for i, c in enumerate(read().strip()):
            if c == '#':
                count_b[i] += 1
            else:
                count_w[i] += 1
    memo = {}
    print(rec(n, count_b, count_w, x, y, 0, 0, 0, memo))



if __name__ == '__main__':
    main()