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. 

Input

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 "#".

Output

In the first line print the minimum number of pixels to repaint. It is guaranteed that the answer exists. 

Examples

Input

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..


Output

11


Input

2 5 1 1
#####
.....


Output

5

Note

In the first test sample the picture after changing some colors can looks as follows: 
    
    
      
    .##..  
    .##..  
    .##..  
    .##..  
    .##..  
    .##..  
    

In the second test sample the picture after changing some colors can looks as follows: 
    
    
      
    .#.#.  
    .#.#.

Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def main():
	(n, m, x, y) = map(int, input().split())
	col = [0] * m
	for i in range(n):
		row = input()
		for j in range(m):
			if row[j] == '.':
				col[j] += 1
	acc = [0]
	for j in range(m):
		acc.append(acc[-1] + col[j])
	dp = [[0] * (m + 1), [0] * (m + 1)]
	for j in range(1, m + 1):
		dp[0][j] = float('infinity')
		dp[1][j] = float('infinity')
		for k in range(x, y + 1):
			if j - k >= 0:
				wp = acc[j] - acc[j - k]
				bp = k * n - wp
				dp[0][j] = min(dp[0][j], dp[1][j - k] + wp)
				dp[1][j] = min(dp[1][j], dp[0][j - k] + bp)
	print(min(dp[0][m], dp[1][m]))
main()


(n, m, x, y) = map(int, input().split())
d = {'#': 0, '.': 1}
l = [[0, 0] for i in range(m)]
for i in range(n):
	s = input()
	for j in range(m):
		l[j][d[s[j]]] += 1
(pb, pw) = ([0], [0])
for i in range(m):
	pb.append(pb[-1] + l[i][0])
	pw.append(pw[-1] + l[i][1])
dp = [[float('inf')] * (m + 1) for i in range(2)]
dp[0][0] = dp[1][0] = 0
for i in range(1, m + 1):
	for j in range(x, y + 1):
		if i - j >= 0:
			dp[0][i] = min(dp[0][i], dp[1][i - j] + pb[i] - pb[i - j])
			dp[1][i] = min(dp[1][i], dp[0][i - j] + pw[i] - pw[i - j])
print(min(dp[0][-1], dp[1][-1]))


import os
from sys import stdin, stdout

def solve(tc):
	(n, m, x, y) = map(int, stdin.readline().split())
	grid = []
	for i in range(n):
		grid.append(list(stdin.readline().strip()))
	dp = [[[n * m, n * m] for j in range(y + 1)] for i in range(m + 1)]
	dp[0][0][0] = dp[0][0][1] = 0
	for i in range(m):
		blacks = 0
		for j in range(n):
			if grid[j][i] == '#':
				blacks += 1
		for k in range(x):
			dp[i + 1][k + 1][0] = min(dp[i + 1][k + 1][0], dp[i][k][0] + n - blacks)
			dp[i + 1][k + 1][1] = min(dp[i + 1][k + 1][1], dp[i][k][1] + blacks)
		for k in range(x, y):
			dp[i + 1][k + 1][0] = min(dp[i + 1][k + 1][0], dp[i][k][0] + n - blacks)
			dp[i + 1][k + 1][1] = min(dp[i + 1][k + 1][1], dp[i][k][1] + blacks)
			dp[i + 1][1][0] = min(dp[i + 1][1][0], dp[i][k][1] + n - blacks)
			dp[i + 1][1][1] = min(dp[i + 1][1][1], dp[i][k][0] + blacks)
		dp[i + 1][1][0] = min(dp[i + 1][1][0], dp[i][y][1] + n - blacks)
		dp[i + 1][1][1] = min(dp[i + 1][1][1], dp[i][y][0] + blacks)
	ans = n * m
	for k in range(x, y + 1):
		ans = min(ans, dp[m][k][0])
		ans = min(ans, dp[m][k][1])
	print(ans)
tcs = 1
tc = 1
while tc <= tcs:
	solve(tc)
	tc += 1


import os, sys
from io import BytesIO, IOBase

def main():
	(n, m, x, y) = map(int, input().split())
	arr = [input().strip() for _ in range(n)]
	a = [[0, 0] for _ in range(m)]
	for j in range(m):
		for i in range(n):
			if arr[i][j] == '.':
				a[j][1] += 1
			else:
				a[j][0] += 1
	dp = [[[10 ** 20, 10 ** 20] for _ in range(y + 2)] for _ in range(m)]
	dp[0][1] = a[0][:]
	for i in range(m - 1):
		for j in range(1, y + 1):
			if j >= x:
				dp[i + 1][1][0] = min(dp[i + 1][1][0], dp[i][j][1] + a[i + 1][0])
				dp[i + 1][1][1] = min(dp[i + 1][1][1], dp[i][j][0] + a[i + 1][1])
			dp[i + 1][j + 1][0] = min(dp[i + 1][j + 1][0], dp[i][j][0] + a[i + 1][0])
			dp[i + 1][j + 1][1] = min(dp[i + 1][j + 1][1], dp[i][j][1] + a[i + 1][1])
	print(min(map(min, dp[m - 1][x:y + 1])))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
from math import inf

def main():
	(n, m, x, y) = [int(x) for x in input().split()]
	cost = [[0, 0] for column in range(m)]
	for row in range(n):
		newRow = input()
		for column in range(m):
			if newRow[column] == '.':
				cost[column][1] += 1
			else:
				cost[column][0] += 1
	dp = [[[inf, inf] for consecutive in range(y + 1)] for column in range(m)]
	dp[0][1][0] = cost[0][0]
	dp[0][1][1] = cost[0][1]
	for column in range(1, m):
		for consecutive in range(1, min(y + 1, column + 2)):
			if consecutive >= x:
				for char in range(2):
					dp[column][1][char] = min(dp[column - 1][consecutive][1 - char] + cost[column][char], dp[column][1][char])
			for char in range(2):
				dp[column][consecutive][char] = min(dp[column - 1][consecutive - 1][char] + cost[column][char], dp[column][consecutive][char])
	answer = inf
	for consecutive in range(x, y + 1):
		for char in range(2):
			answer = min(dp[m - 1][consecutive][char], answer)
	print(answer)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
input = lambda : sys.stdin.readline().rstrip('\r\n')

def print(*args, **kwargs):
	sep = kwargs.pop('sep', ' ')
	file = kwargs.pop('file', sys.stdout)
	atStart = True
	for x in args:
		if not atStart:
			file.write(sep)
		file.write(str(x))
		atStart = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
main()


(n, m, x, y) = map(int, input().split())
s = []
for i in range(n):
	s.append(input())
dp = [[[1e+18, 1e+18] for i in range(y + 1)] for j in range(m)]
ct = [0 for i in range(m)]
for i in range(n):
	for j in range(m):
		if s[i][j] == '.':
			ct[j] += 1
dp[0][1][1] = ct[0]
dp[0][1][0] = n - ct[0]
for i in range(1, m):
	for j in range(1, y + 1):
		dp[i][j][1] = dp[i - 1][j - 1][1] + ct[i]
		dp[i][j][0] = dp[i - 1][j - 1][0] + n - ct[i]
		if j >= x:
			dp[i][1][0] = min(dp[i][1][0], dp[i - 1][j][1] + n - ct[i])
			dp[i][1][1] = min(dp[i][1][1], dp[i - 1][j][0] + ct[i])
ans = 1e+18
for i in range(x, y + 1):
	ans = min(ans, min(dp[-1][i]))
print(ans)


import time, math as mt, bisect, sys
from sys import stdin, stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi = 3.141592653589793

def II():
	return int(stdin.readline())

def IO():
	return stdin.readline()

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def P(x):
	return stdout.write(str(x) + '\n')

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

def lcm(a, b):
	return a * b // gcd(a, b)

def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(a % b, b)
	else:
		return gcd(a, b % a)

def readTree():
	v = int(input())
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = In()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return (adj, v)

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count
mx = 10 ** 7
spf = [mx] * (mx + 1)

def SPF():
	spf[1] = 1
	for i in range(2, mx + 1):
		if spf[i] == mx:
			spf[i] = i
			for j in range(i * i, mx + 1, i):
				if i < spf[j]:
					spf[j] = i
	return
mod = 10 ** 9 + 7

def solve():
	(n, m, x, y) = IP()
	li = [input() for i in range(n)]
	white = [0] * m
	for j in range(m):
		cnt = 0
		for i in range(n):
			if li[i][j] == '.':
				cnt += 1
		white[j] = cnt
	for i in range(1, m):
		white[i] += white[i - 1]
	white.insert(0, 0)
	dp = [[1000000000000.0, 1000000000000.0] for i in range(m + 1)]
	(dp[0][0], dp[0][1]) = (0, 0)
	for i in range(m + 1):
		for j in range(x, y + 1):
			if i - j >= 0:
				dp[i][0] = min(dp[i - j][1] + j * n - (white[i] - white[i - j]), dp[i][0])
				dp[i][1] = min(dp[i - j][0] + white[i] - white[i - j], dp[i][1])
	P(min(dp[m][0], dp[m][1]))
t = 1
for i in range(t):
	solve()


import math
import sys
from bisect import bisect_right, bisect_left, insort_right
from collections import Counter, defaultdict
from heapq import heappop, heappush
from itertools import accumulate, permutations, combinations
from sys import stdout
R = lambda : map(int, input().split())
(n, m, x, y) = R()
(x, y) = (min(m, x), min(m, y))
cs = [[0] * (m + 1), [0] * (m + 1)]
for _ in range(n):
	for (i, c) in enumerate(input()):
		cs[0][i] += c == '#'
		cs[1][i] += c == '.'
dp = [[math.inf] * (m + 1) + [0] for i in range(2)]
dp[0][x - 1] = sum((cs[0][i] for i in range(x)))
dp[1][x - 1] = sum((cs[1][i] for i in range(x)))
for i in range(x, m):
	for t in range(2):
		acc = sum((cs[t][j] for j in range(i, i - x, -1)))
		for j in range(i - x, max(-2, i - y - 1), -1):
			dp[t][i] = min(dp[t][i], acc + dp[1 - t][j])
			acc += cs[t][j]
print(min(dp[0][m - 1], dp[1][m - 1]))


def arr_inp():
	return [int(x) for x in stdin.readline().split()]

def arr_sum(arr):
	arr.appendleft(0)
	return list(accumulate(arr, lambda x, y: x + y))
from collections import *
from sys import stdin
from itertools import accumulate
(n, m, x, y) = arr_inp()
(mem, mat2) = (defaultdict(lambda : float('inf')), [0 for i in range(m)])
for i in range(n):
	row = stdin.readline()[:-1]
	for j in range(m):
		if row[j] == '.':
			mat2[j] += 1
cum = arr_sum(deque(mat2))
(mem[0, 1], mem[0, 0]) = (0, 0)
for i in range(x, m + 1):
	for j in range(x, min(y, m) + 1):
		(plus, plus1) = (n * j - (cum[i] - cum[i - j]), cum[i] - cum[i - j])
		mem[i, 1] = min(mem[i, 1], plus1 + mem[i - j, 0])
		mem[i, 0] = min(mem[i, 0], plus + mem[i - j, 1])
ans = min(mem[m, 1], mem[m, 0])
print(ans)


inf = 9999999999

def f(ll, n, m, x, y):
	W = [0] * m
	for i in range(n):
		for j in range(m):
			if ll[i][j] == '.':
				W[j] += 1
	B = [n - c for c in W]
	Bw = [inf] * (y + 1)
	Ww = [inf] * (y + 1)
	Bw[1] = B[0]
	Ww[1] = W[0]
	Bv = B[0] if x == 1 else inf
	Wv = W[0] if x == 1 else inf
	for i in range(1, m):
		for j in range(y, 0, -1):
			Bw[j] = Bw[j - 1] + B[i]
			Ww[j] = Ww[j - 1] + W[i]
		if Bv < inf:
			Ww[1] = Bv + W[i]
			Bw[1] = Wv + B[i]
		Bv = min(Bw[x:y + 1])
		Wv = min(Ww[x:y + 1])
	return min(Bv, Wv)
(n, m, x, y) = list(map(int, input().split()))
ll = [input() for _ in range(n)]
print(f(ll, n, m, x, y))


import sys
(n, m, x, y) = list(map(int, input().split()))
lis1 = [0] * m
lis2 = [0] * m
for i in range(n):
	s = str(input())
	for j in range(m):
		if s[j] == '#':
			lis1[j] += 1
		else:
			lis2[j] += 1
num1 = [0]
num2 = [0]
for i in range(m):
	num1.append(num1[-1] + lis1[i])
	num2.append(num2[-1] + lis2[i])
dp = [[0] * (m + 1) for i in range(2)]
for i in range(1, m + 1):
	ans1 = sys.maxsize
	ans2 = sys.maxsize
	for j in range(x, y + 1):
		if i - j >= 0:
			temp1 = dp[1][i - j] + num1[i] - num1[i - j]
			temp2 = dp[0][i - j] + num2[i] - num2[i - j]
			ans1 = min(ans1, temp1)
			ans2 = min(ans2, temp2)
	dp[0][i] = ans1
	dp[1][i] = ans2
print(min(dp[0][m], dp[1][m]))


from sys import stdin, stdout

def main():
	(n, m, x, y) = map(int, stdin.readline().split())
	b_pixels = [0] * (m + 1)
	w_pixels = [0] * (m + 1)
	for _ in range(n):
		l = stdin.readline().strip()
		for i in range(len(l)):
			if l[i] == '#':
				b_pixels[i + 1] += 1
			else:
				w_pixels[i + 1] += 1
	for i in range(1, m + 1):
		b_pixels[i] += b_pixels[i - 1]
		w_pixels[i] += w_pixels[i - 1]
	dpw = [1000000000.0] * (m + 1)
	dpb = [1000000000.0] * (m + 1)

	def w(k):
		if k < 0:
			return 1000000000.0
		if k == 0:
			return 0
		if dpw[k] != 1000000000.0:
			return dpw[k]
		cost = 1000000000.0
		for j in range(x, y + 1):
			if k - j < 0:
				break
			paint_white_pixels = w_pixels[k] - w_pixels[k - j]
			paint_rest = b(k - j)
			cost = min(cost, paint_white_pixels + paint_rest)
		dpw[k] = cost
		return cost

	def b(k):
		if k < 0:
			return 1000000000.0
		if k == 0:
			return 0
		if dpb[k] != 1000000000.0:
			return dpb[k]
		cost = 1000000000.0
		for j in range(x, y + 1):
			if k - j < 0:
				break
			paint_black_pixels = b_pixels[k] - b_pixels[k - j]
			paint_rest = w(k - j)
			cost = min(cost, paint_black_pixels + paint_rest)
		dpb[k] = cost
		return cost
	print(min(w(m), b(m)))
main()


(n, m, x, y) = [int(x) for x in input().split()]
col_blacks = [0] * m
for i in range(n):
	cur_str = input()
	for (j, cur_ch) in enumerate(cur_str):
		if cur_ch == '#':
			col_blacks[j] += 1

def get_min_pixels(pos, color, memory={}):
	if (pos, color) in memory:
		return memory[pos, color]
	if color == 'white':
		costs = col_blacks
	else:
		costs = [n - col_black for col_black in col_blacks]
	if pos < m and pos + x > m:
		val = 2 * n * m
		memory[pos, color] = val
		return val
	cur_max_size = min(y, m - pos)
	cumsums = []
	for cost in costs[pos:pos + cur_max_size]:
		if len(cumsums) == 0:
			cumsums.append(cost)
		else:
			cumsums.append(cost + cumsums[-1])
	if len(cumsums) == 0:
		val = 0
		memory[pos, color] = val
		return val
	overall_min = n * m
	next_color = 'white' if color == 'black' else 'black'
	for size in range(x, cur_max_size + 1):
		cur_min = cumsums[size - 1] + get_min_pixels(pos + size, next_color, memory)
		overall_min = min(overall_min, cur_min)
	memory[pos, color] = overall_min
	return overall_min
memory = {}
black_min = get_min_pixels(0, 'black', memory)
white_min = get_min_pixels(0, 'white', memory)
print(min(black_min, white_min))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass
(n, m, x, y) = map(int, input().split())
d = {'#': 0, '.': 1}
l = [[0, 0] for i in range(m)]
for i in range(n):
	s = input()
	for j in range(m):
		l[j][d[s[j]]] += 1
(pb, pw) = ([0], [0])
for i in range(m):
	pb.append(pb[-1] + l[i][0])
	pw.append(pw[-1] + l[i][1])
A = [[float('inf')] * (m + 1) for i in range(2)]
A[0][0] = A[1][0] = 0
for i in range(1, m + 1):
	for j in range(x, y + 1):
		if i - j >= 0:
			A[0][i] = min(A[0][i], A[1][i - j] + pb[i] - pb[i - j])
			A[1][i] = min(A[1][i], A[0][i - j] + pw[i] - pw[i - j])
print(min(A[0][-1], A[1][-1]))
endtime = time.time()


import sys
import math as mt
import bisect
t = 1
for __ in range(t):
	(n, m, x, y) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	yhash = [0] * (m + 1)
	ydot = [0] * (m + 1)
	j1 = 1
	for j in range(m):
		cnt = 0
		for i in range(n):
			if l[i][j] == '#':
				cnt += 1
		yhash[j1] = cnt + yhash[j1 - 1]
		ydot[j1] = n - cnt + ydot[j1 - 1]
		j1 += 1
	dp = [[0 for i in range(m + 1)] for j in range(2)]
	for i in range(1, m + 1):
		mini = 10 ** 6
		for j in range(x, y + 1):
			if i - j >= 0:
				mini = min(dp[0][i - j] + yhash[i] - yhash[i - j], mini)
		dp[1][i] = mini
		mini = 10 ** 6
		for j in range(x, y + 1):
			if i - j >= 0:
				mini = min(dp[1][i - j] + ydot[i] - ydot[i - j], mini)
		dp[0][i] = mini
	print(min(dp[0][m], dp[1][m]))


import sys
from math import log2, floor, ceil, sqrt, gcd
import bisect
sys.setrecursionlimit(10 ** 5)
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 1000000007
(n, m, x, y) = Ri()
lis = []
for i in range(n):
	temp = ri()
	lis.append(temp)
black = [0] * m
white = [0] * m
preb = [0] * (m + 1)
prew = [0] * (m + 1)
for j in range(m):
	cnt = 0
	for i in range(n):
		if lis[i][j] == '#':
			cnt += 1
	black[j] = cnt
	white[j] = n - cnt
	preb[j + 1] = preb[j] + black[j]
	prew[j + 1] = prew[j] + white[j]
dp = list2d(2, m + 1, INF)
dp[0][0] = dp[1][0] = 0
for i in range(m):
	if i - x + 1 < 0:
		continue
	for j in range(max(i - x + 1, 0), max(i - y + 1, 0) - 1, -1):
		dp[0][i + 1] = min(dp[0][i + 1], prew[i + 1] - prew[j] + dp[1][j])
		dp[1][i + 1] = min(dp[1][i + 1], preb[i + 1] - preb[j] + dp[0][j])
print(min(dp[0][m], dp[1][m]))


a = [int(i) for i in input().split()]
b = [0] * a[1]
(h, j) = (9999999999, 9999999999)
for i in range(0, a[0]):
	c = input()
	for p in range(0, a[1]):
		if c[p] == '#':
			b[p] += 1
n = {1: a[0] - b[0]}
w = {1: b[0]}
for i in range(2, a[1] + 1):
	try:
		h = min([w[y] for y in w][a[2] - 1:]) + a[0] - b[i - 1]
		j = min([n[y] for y in n][a[2] - 1:]) + b[i - 1]
	except:
		pass
	if i >= a[3]:
		l = a[3]
	else:
		l = i
	for z in range(l, 1, -1):
		n[z] = n[z - 1] + a[0] - b[i - 1]
		w[z] = w[z - 1] + b[i - 1]
	n[1] = h
	w[1] = j
print(min([n[i] for i in n][a[2] - 1:] + [w[i] for i in w][a[2] - 1:]))


import math
(n, m, x, y) = map(int, input().split())
cost = [[0 for i in range(m)] for i in range(2)]
for i in range(n):
	s = input()
	for i in range(len(s)):
		if s[i] == '#':
			cost[1][i] += 1
		else:
			cost[0][i] += 1
fin = [[math.inf for i in range(m + 1)] for i in range(2)]
pre = [[0 for i in range(m + 1)] for i in range(2)]
fin[0][0] = 0
fin[1][0] = 0
for i in range(1, m + 1):
	if i == 1:
		pre[0][i] = cost[0][i - 1]
		pre[1][i] = cost[1][i - 1]
	else:
		pre[0][i] = pre[0][i - 1] + cost[0][i - 1]
		pre[1][i] = pre[1][i - 1] + cost[1][i - 1]
for i in range(1, m + 1):
	if i < 2 * x:
		fin[0][i] = pre[0][i]
		fin[1][i] = pre[1][i]
	else:
		cont = x
		while cont <= y:
			if i <= y:
				fin[0][i] = min(fin[0][i], pre[0][i])
				fin[1][i] = min(fin[1][i], pre[1][i])
			if i - cont < x:
				break
			fin[0][i] = min(fin[0][i], fin[1][i - cont] + pre[0][i] - pre[0][i - cont])
			fin[1][i] = min(fin[1][i], fin[0][i - cont] + pre[1][i] - pre[1][i - cont])
			cont += 1
print(min(fin[0][-1], fin[1][-1]))


(n, m, x, y) = map(int, input().split())
u = [i.count('.') for i in list(zip(*[input() for i in range(n)]))]
v = [n - i for i in u]
(a, b, s) = ([u[0]], [v[0]], x - 1)
for i in range(1, x):
	(a, b) = ([1000001] + [j + u[i] for j in a], [1000001] + [j + v[i] for j in b])
for i in range(x, min(y, m)):
	(a, b) = ([min(b[s:]) + u[i]] + [j + u[i] for j in a], [min(a[s:]) + v[i]] + [j + v[i] for j in b])
for i in range(min(y, m), m):
	(a, b) = ([min(b[s:]) + u[i]] + [j + u[i] for j in a[:-1]], [min(a[s:]) + v[i]] + [j + v[i] for j in b[:-1]])
print(min(min(a[s:]), min(b[s:])))


import sys

def DP(curPos, color, placing, x, y, grid):
	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]
	cache[0][1][1] = grid[0][0]
	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))
	return simpleGrid

def solve(n, m, x, y, grid):
	intGrid = readGrid(grid)
	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()


from math import inf
(n, m, x, y) = map(int, input().split())
matx = []
for i in range(n):
	matx.append(list(input().strip()))
d = [[0, 0]]
for i in range(m):
	c = 0
	for j in range(n):
		if matx[j][i] == '.':
			c += 1
	d.append([c, n - c])
for i in range(1, m + 1):
	d[i][0] += d[i - 1][0]
	d[i][1] += d[i - 1][1]
dp = [[inf, inf] for j in range(m + 1)]
dp[0] = [0, 0]
dp[x] = [d[x][0], d[x][1]]
for i in range(x, m + 1):
	for j in range(x, min(y + 1, i + 1)):
		dp[i][0] = min(dp[i - j][1] + d[i][0] - d[i - j][0], dp[i][0])
		dp[i][1] = min(dp[i - j][0] + d[i][1] - d[i - j][1], dp[i][1])
print(min(dp[-1]))


param1 = str(input()).split()
(n, m, x, y) = [int(i) for i in param1]
grid = []
count = []
for i in range(n):
	row = str(input())
	grid.append(row)
for i in range(m):
	count_m = 0
	for j in range(n):
		if grid[j][i] == '#':
			count_m += 1
	count.append(count_m)
count_sum = [0 for i in range(m)]
count_sum_2 = [0 for i in range(m)]
count_sum[0] = count[0]
count_sum_2[0] = n - count[0]
for i in range(1, m):
	count_sum[i] = count_sum[i - 1] + count[i]
	count_sum_2[i] = count_sum_2[i - 1] + (n - count[i])
MAX = 1000000
dp1 = [[0 for i in range(y + 2 - x)] for j in range(m)]
dp2 = [[0 for i in range(y + 2 - x)] for j in range(m)]
dp3 = [0 for i in range(m)]
dp4 = [0 for i in range(m)]
for i in range(m):
	min_1 = MAX
	min_2 = MAX
	for index in range(x, y + 1):
		r = index - x + 1
		if i + 1 < index:
			continue
		if i < index:
			dp1[i][r] = count_sum[i]
			dp2[i][r] = count_sum_2[i]
		else:
			dp1[i][r] = count_sum[i] - count_sum[i - index] + dp3[i - index]
			dp2[i][r] = count_sum_2[i] - count_sum_2[i - index] + dp4[i - index]
		min_1 = min(min_1, dp1[i][r])
		min_2 = min(min_2, dp2[i][r])
	dp3[i] = min_2
	dp4[i] = min_1
if dp3[m - 1] < dp4[m - 1]:
	print(dp3[m - 1])
else:
	print(dp4[m - 1])


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, M, X, Y, A):
	Y = min(Y, M)
	whites = []
	for c in range(M):
		w = sum([1 if A[r][c] == '.' else 0 for r in range(N)])
		whites.append(w)
	black = [N - v for v in whites]
	dp = [[[N * M for _ in range(2)] for _ in range(Y + 1)] for _ in range(M)]
	dp[0][1][0] = black[0]
	dp[0][1][1] = whites[0]
	for c in range(1, M):
		dp[c][1][0] = min([dp[c - 1][y][1] + black[c] for y in range(X, Y + 1)])
		dp[c][1][1] = min([dp[c - 1][y][0] + whites[c] for y in range(X, Y + 1)])
		for y in range(2, Y + 1):
			dp[c][y][0] = dp[c - 1][y - 1][0] + black[c]
			dp[c][y][1] = dp[c - 1][y - 1][1] + whites[c]
	ans = N * M
	for y in range(X, Y + 1):
		ans = min(ans, min(dp[M - 1][y]))
	return ans
(N, M, X, Y) = map(int, input().split())
A = []
for i in range(N):
	A.append(input())
print(solve(N, M, X, Y, A))


import sys
import heapq
import math
sys.setrecursionlimit(100000)
from collections import deque
from collections import defaultdict
from collections import Counter

def PRINT(lst, sep=' '):
	print(sep.join(map(str, lst)))
I = lambda : list(map(int, input().split(' ')))

def solve():
	return
(n, m, x, y) = I()
bar = [list(input()) for _ in range(n)]

def COL(k):
	return [bar[i][k] for i in range(n)]
row = []
for i in range(m):
	c = dict(Counter(COL(i)))
	row.append(c['#'] if '#' in c else 0)
s_arr = [0]
for r in row:
	s_arr.append(s_arr[-1] + r)

def SUM(l, r):
	return s_arr[r + 1] - s_arr[l]
mem = {}
import time
global arr

def rec(start, color):
	if (start, color) in mem:
		return mem[start, color]
	elif start == m:
		return 0
	mm = float('inf')
	for end in range(start + x - 1, start + y):
		if end >= m:
			continue
		ss = SUM(start, end) if color == 'b' else (end - start + 1) * n - SUM(start, end)
		mm = min(mm, ss + rec(end + 1, 'w' if color == 'b' else 'b'))
	mem[start, color] = mm
	return mm
print(min(rec(0, 'w'), rec(0, 'b')))


(n, m, x, y) = map(int, input().split())
cnt = [0] * m
for i in range(n):
	s = input()
	for j in range(m):
		if s[j] == '#':
			cnt[j] += 1
pre = [[0, 0]]
for i in cnt:
	pre.append([pre[-1][0] + i, pre[-1][1] + n - i])
dp = [None] * (m + 1)
dp[0] = [0, 0]
for i in range(m):
	dp[i + 1] = [int(1000000.0), int(1000000.0)]
for i in range(m):
	for j in range(x, y + 1):
		try:
			if i + j <= m:
				dp[i + j][0] = min(dp[i][1] + pre[i + j][0] - pre[i][0], dp[i + j][0])
				dp[i + j][1] = min(dp[i + j][1], dp[i][0] + pre[i + j][1] - pre[i][1])
		except:
			print(i, j)
print(min(dp[m][0], dp[m][1]))


def mem(ind, cnt, f):
	if ind == m:
		if cnt >= x:
			return 0
		else:
			return 1e+18
	if dp[ind][cnt][f] != -1:
		return dp[ind][cnt][f]
	ans = 1e+18
	if f == 0:
		val = n - ct[ind]
	else:
		val = ct[ind]
	if cnt >= x:
		ans = min(ans, mem(ind + 1, 1, f ^ 1) + n - val)
	if cnt < y:
		ans = min(ans, mem(ind + 1, cnt + 1, f) + val)
	dp[ind][cnt][f] = ans
	return dp[ind][cnt][f]
(n, m, x, y) = map(int, input().split())
s = []
for i in range(n):
	s.append(input())
dp = [[[-1, -1] for i in range(y + 1)] for j in range(m)]
ct = [0 for i in range(m)]
for i in range(n):
	for j in range(m):
		if s[i][j] == '.':
			ct[j] += 1
print(min(mem(0, 0, 0), mem(0, 0, 1)))


import sys
from functools import lru_cache
from collections import defaultdict

def query(i, j):
	if i == 0:
		black = cum_cols[j]
	else:
		black = cum_cols[j] - cum_cols[i - 1]
	white = (j - i + 1) * len(mat) - black
	return (black, white)

def main(x, y):
	num_cols = len(mat[0])
	DP = {}

	def dp(j, color):
		if j >= num_cols:
			return 0
		return DP[j, color]
	for j in range(num_cols - 1, -1, -1):
		bb = float('inf')
		bw = float('inf')
		for p in range(x, y + 1):
			if j + p - 1 >= num_cols:
				continue
			(b, w) = query(j, j + p - 1)
			bb = min(bb, w + dp(j + p, 'w'))
			bw = min(bw, b + dp(j + p, 'b'))
		DP[j, 'b'] = bb
		DP[j, 'w'] = bw
	return min(dp(0, 'b'), dp(0, 'w'))
mat = []
for (e, line) in enumerate(sys.stdin.readlines()):
	if e == 0:
		(_, _, x, y) = map(int, line.strip().split())
	else:
		mat.append([c for c in line.strip()])
cols = [0 for _ in range(len(mat[0]))]
for i in range(len(mat)):
	for j in range(len(mat[i])):
		if mat[i][j] == '#':
			cols[j] += 1
cum_cols = [cols[0]]
for i in range(1, len(cols)):
	cum_cols.append(cum_cols[-1] + cols[i])
print(main(x, y))


(n, m, x, y) = map(int, input().split())
arr = []
for _ in range(n):
	a = input()
	arr.append(a)
nums = [[0, 0] for i in range(m)]
cost = [[0, 0] for i in range(m)]
for i in range(m):
	b = 0
	w = 0
	for j in range(n):
		if arr[j][i] == '.':
			w += 1
		else:
			b += 1
	nums[i][0] = b
	nums[i][1] = w
	cost[i][1] = b
	cost[i][0] = w
memo = [[[-1 for k in range(m)] for j in range(2)] for i in range(m)]

def dp(i, p, l):
	if i <= m:
		if i == m:
			if l >= x and l <= y:
				return 0
			else:
				return 10 ** 9
		elif l >= x and l <= y:
			if p == 0:
				if memo[i][p][l] != -1:
					return memo[i][p][l]
				else:
					memo[i][p][l] = min(cost[i][0] + dp(i + 1, 0, l + 1), cost[i][1] + dp(i + 1, 1, 1))
					return memo[i][p][l]
			elif memo[i][p][l] != -1:
				return memo[i][p][l]
			else:
				memo[i][p][l] = min(cost[i][1] + dp(i + 1, 1, l + 1), cost[i][0] + dp(i + 1, 0, 1))
				return memo[i][p][l]
		elif l < x:
			if memo[i][p][l] != -1:
				return memo[i][p][l]
			else:
				memo[i][p][l] = cost[i][p] + dp(i + 1, p, l + 1)
				return memo[i][p][l]
		elif l > y:
			return 10 ** 9
	else:
		return 10 ** 9
final = min(dp(0, 0, 0), dp(0, 1, 0))
print(final)


(row, col, x, y) = map(int, input().strip().split())
mat = []
for i in range(row):
	mat.append(list(input()))
(black_pre, white_pre) = ([0 for i in range(col + 1)], [0 for i in range(col + 1)])
for j in range(1, col + 1):
	w = 0
	b = 0
	for i in range(row):
		if mat[i][j - 1] == '.':
			w += 1
		else:
			b += 1
	black_pre[j] += black_pre[j - 1] + b
	white_pre[j] += white_pre[j - 1] + w
dp = [[float('inf') for i in range(col + 1)] for i in range(2)]
dp[0][0] = 0
dp[1][0] = 0
for i in range(1, col + 1):
	for j in range(x, y + 1):
		if i - j >= 0:
			dp[0][i] = min(dp[0][i], dp[1][i - j] + white_pre[i] - white_pre[i - j])
			dp[1][i] = min(dp[1][i], dp[0][i - j] + black_pre[i] - black_pre[i - j])
print(min(dp[0][-1], dp[1][-1]))