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, last_used, width, memo) -> int:
    if col >= n:
        # If we reached the end and the current width is invalid
        if 0 <= width < x or width > y:
            return float('inf')
        return 0
    k = (col, last_used, width)
    if k in memo:
        return memo[k]
    cost_removing_b = count_b[col]
    cost_removing_w = count_w[col]

    if not last_used:
        width_w = 0
        width_b = 0

    else:
        width_w: int= 0 if last_used == 'b' else width
        width_b: int= 0 if last_used == 'w' else width
    removing_w = removing_b = float('inf')
    # Continue expanding until it is no longer valid
    if not last_used or last_used == 'b' or (last_used == 'w' and x <= width or width >= y):
        removing_w = cost_removing_w + rec(n, count_b, count_w, x, y, col + 1, 'b', width_b + 1, memo)
    if not last_used or last_used == 'w' or (last_used == 'b' and x <= width or width >= y):
        removing_b = cost_removing_b + rec(n, count_b, count_w, x, y, col + 1, 'w', width_w + 1, memo)
    val = min(removing_w, removing_b)
    print(removing_w, removing_b, 'for row ', col)
    memo[k] = val
    return val


def prefix_sum(i, j, arr):
    if j - 1 < 0:
        return arr[i]
    return arr[i] - arr[j - 1]

def main() -> None:
    read: Callable[[], str] = sys.stdin.readline
    m, n, x, y = (int(i) for i in read().split())
    count_w = [0] * n
    # Find the number of white cells per column. If a given row has x white, it will have n - x black
    for _ in range(m):
        for i, c in enumerate(read().strip()):
            if c != '#':
                count_w[i] += 1

    # Compute prefix sum array based on count w
    num_of_whites = [0] * (n + 1)
    num_of_whites[1] = count_w[0]  # 1 based arr
    for i in range(1, n):
        num_of_whites[i + 1] = count_w[i] + num_of_whites[i]

    matrix = [[0 for _ in range(n + 1)] for _ in range(2)]
    # We make a decision column by column
    # For each col, we need to determine what cost less, either if the last col is white or if the last col is black
    # We let row = 0 mean that the last column is white
    # If the row is 1, it means that the last column is black
    for i in range(1, n + 1):
        # We only consider valid widths
        for j in range(x, y + 1):
            j -= 1
            if i - j < 0:
                continue
            # Find how much it cost to convert the cols from [j..i - 1] to black, and do the same for white
            cost_paint_black = prefix_sum(i - 1, j, num_of_whites)
            cost_paint_white = ((i - 1) - j + 1) * m - cost_paint_black
            # cost of curr col being white
            matrix[0][i] = min(cost_paint_white, matrix[1][i-1]) + count_w[i - 1]
            matrix[1][i] = min(cost_paint_black, matrix[0][i-1]) + (m - count_w[i - 1])
            print(cost_paint_black, cost_paint_white)

    print(min(matrix[0][-1], matrix[1][-1]))
    # memo = {}
    # print(rec(n, count_b, count_w, x, y, 0, None, 0, memo))
    # print(memo)
    # matri
    # def prefix_sum



if __name__ == '__main__':
    main()