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


def DP(curPos, color, placing, x, y, grid):
    # since readGrid is represented by (white, black), color is rep.
    # by 0 and 1. if color is 0 (white), we need to turn the BLACK squares
    # white (grid[1], so we should lookup color^1.
    if curPos == 0:
        if x <= placing <= y:
            return grid[curPos][color ^ 1]
        else:
            return 10000000

    if (curPos, color, placing) in cache:
        return cache[curPos, color, placing]

    if placing < x:
        total = DP(curPos - 1, color, placing + 1, x, y, grid)
    elif placing == y:
        total = DP(curPos - 1, (color + 1) % 2, 1, x, y, grid)
    else:
        total = min(
            DP(curPos - 1, color, placing + 1, x, y, grid),
            DP(curPos - 1, (color + 1) % 2, 1, x, y, grid),
        )

    total += grid[curPos][color ^ 1]
    cache[curPos, color, placing] = total
    return total


def iterativeDP(m, x, y, grid):

    cache = [[[0 for _ in range(y + 1)] for _ in range(2)] for _ in range(m)]

    for j in range(2):
        for i in range(len(cache[0][0])):
            cache[0][j][i] = 1000000

    cache[0][0][1] = grid[0][
        1
    ]  # 0 for white, meaning "1" is all black squares that need to be turned white
    cache[0][1][1] = grid[0][0]  # 1 for black

    for i in range(1, m):
        for k in range(1, y):
            cache[i][0][k + 1] = cache[i - 1][0][k] + grid[i][1]
            cache[i][1][k + 1] = cache[i - 1][1][k] + grid[i][0]
        cache[i][0][1] = min(cache[i - 1][1][x : y + 1]) + grid[i][1]
        cache[i][1][1] = min(cache[i - 1][0][x : y + 1]) + grid[i][0]

    return min(min(cache[m - 1][0][x : y + 1]), min(cache[m - 1][1][x : y + 1]))


def readGrid(grid):
    simpleGrid = []
    for i in range(len(grid[0])):
        colHash = 0
        colDot = 0
        for j in range(len(grid)):
            if grid[j][i] == "#":
                colHash += 1
            else:
                colDot += 1
        simpleGrid.append((colDot, colHash))  # representing (white, black)

    return simpleGrid


def solve(n, m, x, y, grid):
    intGrid = readGrid(grid)
    #ans = min(DP(m - 1, 0, 1, x, y, intGrid), DP(m - 1, 1, 1, x, y, intGrid))
    ans2 = iterativeDP(m, x, y, intGrid)
    return ans2


def readinput():
    n, m, x, y = map(int, sys.stdin.readline().rstrip().split(" "))
    grid = []
    for _ in range(n):
        line = [i for i in sys.stdin.readline().rstrip()]
        grid.append(line)
    print(solve(n, m, x, y, grid))


readinput()
