problem

President K decided to make a flag for IOI 2016 in Russia. Chairman K first took out the old flag from the warehouse. This flag is divided into squares of N rows and M columns, and each square is painted in one of white, blue, and red.

Chairman K is trying to repaint some of the squares on this flag to make it the Russian flag. However, the Russian flag in this problem is as follows.

* Several lines (one or more lines) from the top are all painted in white.
* The next few lines (one or more lines) are all painted in blue.
* All the cells in the other lines (one or more lines) are painted in red.



Find the minimum number of squares that President K needs to repaint to turn the old flag into a Russian flag.

input

The input consists of 1 + N lines.

On the first line, two integers N and M (3 ≤ N ≤ 50, 3 ≤ M ≤ 50) are written separated by a blank. This means that the flags are separated by N rows and M columns.

The following N lines each contain a string of M characters, which represents the color information painted in the squares of the old flag. The jth character (1 ≤ i ≤ N, 1 ≤ j ≤ M) on the i-th line of the N-line represents the color of the cell on the i-th line and j-th column of the old flag. It is either B'or'R'. 'W' stands for white,'B' stands for blue, and'R' stands for red.

output

Output in one line the minimum number of squares that President K needs to repaint to turn the old flag into a Russian flag.

Input / output example

Input example 1


4 5
WRWRW
BWRWB
WRWRW
RWBWR


Output example 1


11


Input example 2


6 14
WWWWWWWWWWWWWW
WBBBWWRRWWBBBW
WWBWWRRRRWWBWW
BWBWWRRRRWWBWW
WBBWWWRRWWBBBW
WWWWWWWWWWWWWW


Output example 2


44


In I / O example 1, the old flag is colored as shown in the figure below.

fig01

In the figure below, repaint the 11 squares with an'X'.

fig02

This makes it possible to make the Russian flag as shown in the figure below.

fig03

Since it is not possible to make a Russian flag by repainting less than 11 squares, 11 is output.

In I / O example 2, the old flag is colored as shown in the figure below.

fig04

Creative Commons License

Information Olympics Japan Committee work "15th Japan Information Olympics JOI 2015/2016 Qualifying Competition Tasks"





Example

Input

4 5
WRWRW
BWRWB
WRWRW
RWBWR


Output

11

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
inf = float('inf')
(N, M) = map(int, input().split())
flag = [list(str(input())) for i in range(N)]
WBR = []
for i in range(N):
	w = flag[i].count('W')
	b = flag[i].count('B')
	r = flag[i].count('R')
	WBR.append([w, b, r])
ans = inf
for w in range(N - 2):
	for b in range(N - 1):
		if w >= b:
			pass
		else:
			kari = 0
			for i in range(N):
				if i <= w:
					kari += M - WBR[i][0]
				elif i <= b:
					kari += M - WBR[i][1]
				else:
					kari += M - WBR[i][2]
			ans = min(ans, kari)
print(ans)


(n, m) = map(int, input().split())
flag = []
for _ in range(n):
	string = list(input())
	flag.append(string)
ans = 10 ** 9
for white in range(1, n - 1):
	for blue in range(1, n - 1):
		red = n - white - blue
		if red <= 0:
			continue
		cnt = 0
		for i in range(white):
			for j in range(m):
				if flag[i][j] != 'W':
					cnt += 1
		for i in range(blue):
			for j in range(m):
				if flag[white + i][j] != 'B':
					cnt += 1
		for i in range(red):
			for j in range(m):
				if flag[white + blue + i][j] != 'R':
					cnt += 1
		if ans > cnt:
			ans = cnt
print(ans)


def getPaintCount(string, color):
	return len(string) - string.count(color)
(N, M) = map(int, input().split())
A = []
cnt = 0
for i in range(N):
	s = input().strip()
	if i == 0:
		cnt += getPaintCount(s, 'W')
	elif i == N - 1:
		cnt += getPaintCount(s, 'R')
	else:
		A.append(s)
B = []
for w in range(0, N - 1):
	for b in range(1, N - w):
		r = N - 2 - w - b
		if r >= 0:
			B.append([w, b, N - 2 - w - b])
minmin = 2500
cnt2 = 0
for b in B:
	for i in range(len(A)):
		if i < b[0]:
			cnt2 += getPaintCount(A[i], 'W')
		elif b[0] <= i < b[0] + b[1]:
			cnt2 += getPaintCount(A[i], 'B')
		elif b[0] + b[1] <= i < b[0] + b[1] + b[2]:
			cnt2 += getPaintCount(A[i], 'R')
	if cnt2 < minmin:
		minmin = cnt2
	cnt2 = 0
print(cnt + minmin)


(h, w) = [int(s) for s in input().split(' ')]
flag = [input() for i in range(h)]
mincnt = 1145141919810
for i in range(1, h - 1):
	for j in range(1, h - i):
		cnt = 0
		wr = flag[:i]
		br = flag[i:i + j]
		rr = flag[i + j:]
		for l in wr:
			for c in l:
				if c != 'W':
					cnt += 1
		for l in br:
			for c in l:
				if c != 'B':
					cnt += 1
		for l in rr:
			for c in l:
				if c != 'R':
					cnt += 1
		if cnt < mincnt:
			mincnt = cnt
print(mincnt)


str_N_M = input()
(N, M) = map(int, str_N_M.split(' '))
old_flag = []
for i in range(1, N + 1):
	old_flag.append(input())
X = 2500
for white_row in range(1, N - 1):
	for blue_row in range(white_row + 1, N):
		paint_square = 0
		for row in old_flag[:white_row]:
			list_row_w = list(row)
			for moji_w in list_row_w:
				if moji_w == 'B' or moji_w == 'R':
					paint_square += 1
		for row in old_flag[white_row:blue_row]:
			list_row_b = list(row)
			for moji_z in list_row_b:
				if moji_z == 'W' or moji_z == 'R':
					paint_square += 1
		for row in old_flag[blue_row:]:
			list_row_r = list(row)
			for moji_r in list_row_r:
				if moji_r == 'B' or moji_r == 'W':
					paint_square += 1
		if paint_square < X:
			X = paint_square
print(X)


(n, m) = map(int, input().split())
flag = [list(input()) for _ in range(n)]
w = []
b = []
r = []
for i in flag:
	w.append(i.count('W'))
	b.append(i.count('B'))
	r.append(i.count('R'))
ans = 10 ** 18
for x in range(1, n - 1):
	for y in range(x + 1, n):
		ans = min(ans, sum(b[:x]) + sum(r[:x]) + sum(w[x:y]) + sum(r[x:y]) + sum(w[y:]) + sum(b[y:]))
print(ans)


(N, M) = [int(i) for i in input().split(' ')]
blue = [0]
white = [0]
red = [0]
for i in range(N):
	S = input()
	blue.append(M - S.count('B') + blue[-1])
	white.append(M - S.count('W') + white[-1])
	red.append(M - S.count('R') + red[-1])

def paint(i, j):
	retval = 0
	retval += white[i] - white[0]
	retval += blue[j] - blue[i]
	retval += red[N] - red[j]
	return retval
retval = 10 ** 10
for i in range(1, N):
	for j in range(i + 1, N):
		retval = min(paint(i, j), retval)
print(retval)


(n, m) = map(int, input().split())
w = []
b = []
r = []
for i in range(n):
	s = input()
	w.append(m - s.count('W'))
	b.append(m - s.count('B'))
	r.append(m - s.count('R'))
ans = 3000
for i in range(1, n - 1):
	for j in range(i, n - 1):
		ans = min(ans, sum(w[:i]) + sum(b[i:j + 1]) + sum(r[j + 1:]))
print(ans)


inf = 10 ** 20
(n, m) = map(int, input().split())
flist = []
wbrnum = {}
for i in range(n):
	a = list(str(input()))
	flist.append(a)
	b = []
	b.append(a.count('W'))
	b.append(a.count('B'))
	b.append(a.count('R'))
	wbrnum[i] = b
cnt = inf
for i in range(n - 2):
	cnti = 0
	for l in range(i + 1):
		cnti += wbrnum[l][1] + wbrnum[l][2]
	for j in range(i + 1, n - 1):
		cntj = 0
		cnto = 0
		for o in range(i + 1, j + 1):
			cntj += wbrnum[o][0] + wbrnum[o][2]
		for o in range(j + 1, n):
			cnto += wbrnum[o][0] + wbrnum[o][1]
		cnt = min(cnt, cnti + cntj + cnto)
print(cnt)


def differ(i, ss):
	tos = ['W', 'B', 'R']
	count = 0
	for j in ss:
		if j != tos[i]:
			count += 1
	return count
[n, m] = list(map(int, input().split()))
ls = []
for i in range(n):
	ls.append(input())
dp = [[0 for i in range(50)] for i in range(3)]
dp[0][0] = differ(0, ls[0])
for i in range(3):
	for j in range(n):
		if j == 0:
			if i == 0:
				dp[i][j] = differ(0, ls[0])
			else:
				dp[i][j] = 100000
		elif i == 0:
			dp[i][j] = dp[i][j - 1] + differ(i, ls[j])
		else:
			dp[i][j] = min(dp[i - 1][j - 1] + differ(i, ls[j]), dp[i][j - 1] + differ(i, ls[j]))
print(dp[2][n - 1])


(h, w) = map(int, input().split())
f = [0 for _ in range(h)]
for i in range(h):
	f[i] = input()
cw = [f[i].count('W') for i in range(h)]
cb = [f[i].count('B') for i in range(h)]
cr = [f[i].count('R') for i in range(h)]
count = h * w
for i in range(1, h - 1):
	for j in range(i, h):
		count = min(count, h * w - sum(cw[:i]) - sum(cb[i:j]) - sum(cr[j:]))
print(count)


(n, m) = map(int, input().split())
f_lis = []
for i in range(n):
	f_lis.append(list(str(input())))
ans_lis = []
W_num = []
W_cou = 0
B_num = []
B_cou = 0
R_num = []
R_cou = 0
for k in range(0, n):
	W_cou += f_lis[k].count('B') + f_lis[k].count('R')
	W_num.append(W_cou)
for k in range(0, n):
	B_cou += f_lis[k].count('W') + f_lis[k].count('R')
	B_num.append(B_cou)
for k in range(0, n):
	R_cou += f_lis[k].count('B') + f_lis[k].count('W')
	R_num.append(R_cou)
for i in range(1, n - 1):
	for j in range(i + 1, n):
		ans_lis.append(W_num[i - 1] + B_num[j - 1] - B_num[i - 1] + R_num[n - 1] - R_num[j - 1])
print(min(ans_lis))


(N, M) = list(map(int, input().split(' ')))
colors = []
for i in range(N):
	row = list(input())
	row_color = [0, 0, 0]
	for c in row:
		if c == 'W':
			row_color[0] += 1
		elif c == 'B':
			row_color[1] += 1
		elif c == 'R':
			row_color[2] += 1
	colors.append(row_color)
min_diff = float('inf')
for blue_top in range(1, N - 1):
	for red_top in range(blue_top + 1, N):
		diff = 0
		for i in range(N):
			if i < blue_top:
				diff += colors[i][1] + colors[i][2]
			elif i < red_top:
				diff += colors[i][0] + colors[i][2]
			else:
				diff += colors[i][0] + colors[i][1]
		if diff < min_diff:
			min_diff = diff
print(min_diff)