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
sys.setrecursionlimit(95000)

def solve(arr,m,x,y,f,last,d):
    if(m==0):
        return 0
    if((m,f,last) in d):
        return d[(m,f,last)]
    if(f<x and last=="*"):
        temp=min(arr[m-1][1]+solve(arr,m-1,x,y,f+1,".",d),arr[i][0]+solve(arr,m-1,x,y,f+1,"#",d))
    elif(f<x):
        if(last=="."):
            temp=arr[m-1][1]+solve(arr,m-1,x,y,f+1,".",d)
        else:
            temp=arr[m-1][0]+solve(arr,m-1,x,y,f+1,"#",d)
    elif(f>=x and f<y):
        if(last=="."):
            temp=min(arr[m-1][1]+solve(arr,m-1,x,y,f+1,last,d),arr[m-1][0]+solve(arr,m-1,x,y,1,"#",d))
        else:
            temp=min(arr[m-1][0]+solve(arr,m-1,x,y,f+1,last,d),arr[m-1][1]+solve(arr,m-1,x,y,1,".",d))
    elif(f==y):
        if(last=="."):
            temp=arr[m-1][0]+solve(arr,m-1,x,y,1,"#",d)
        else:
            temp=arr[m-1][1]+solve(arr,m-1,x,y,1,".",d)
    d[(m,f,last)]=temp        
    return  temp 
            

arr=[int(x) for x in input().split()]
n,m,x,y=arr[0],arr[1],arr[2],arr[3]
arr=[[0,0] for i in range(m)]
for i in range(n):
    s=list(input())
    
    for i in range(m):
        if(s[i]=="."):
            arr[i][0]+=1
        else:
            arr[i][1]+=1
d={}            
print(solve(arr,m,x,y,0,"*",d)) 
