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 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 = [[float('inf') for _ in range(n + 1)] for _ in range(2)]
    matrix[0][0] = 0
    matrix[1][0] = 0
    # We make a decision column by column
    # We let row = 0 mean that the last column is white
    # If the row is 1, it means that the last column is black
    # And let matrix[i][j] = min number of repainted cells where the last column is color i
    for i in range(1, n + 1):
        # We only consider valid widths (note that it needs to be inclusive on y), let j be the current width we are
        # considering.
        for width in range(x, y + 1):
            # Find the start point based on the width
            start = i - (width - 1)
            if start < 0:
                break
            # Find how much it cost to convert the cols from [start..i] to black, and do the same for white
            cost_paint_black = prefix_sum(i, start, num_of_whites)
            cost_paint_white = (i - start + 1) * m - cost_paint_black
            # We are repainting col i to be white, so the total cost for the current width will be the cost of the 
            # columns [start..i] to be painted white + the cost of the col before start to be black
            matrix[0][i] = min(matrix[0][i], cost_paint_white + matrix[1][start - 1])
            # We are repainting col i to be black
            matrix[1][i] = min(matrix[1][i], cost_paint_black + matrix[0][start - 1])
    print(min(matrix[0][-1], matrix[1][-1]))



if __name__ == '__main__':
    main()