Read problems statements in [Mandarin Chinese], [Russian], and [Bengali] as well.

A programming competition will be held in Chef's city which only accepts teams of size 2. At least one person in a team should know a programming language and at least one person should know about the English language. It is possible that one person in a team knows both programming and the English language. Then the qualification of the other teammate is not important i.e. he may or may not know programming and English. Now Chef has N students and wants to send *maximum* number of teams to the competition.

You are given an integer N and two binary strings S and T of length N. S_{i} =  '1' denotes that the i^{th} student knows a programming language, and S_{i} =  '0' denotes otherwise; similarly, T_{i} = '1' denotes that the i^{th} student knows English language, and T_{i} =  '0' denotes otherwise. Determine the maximum number of teams Chef can form.

------ Input Format ------ 

- The first line of input contains a single integer Q denoting the number of test cases. The description of Q test cases follows.
- Each test case contains 3 lines of input.
- The first line of each test case contains an integer N.
- The second line of each test case contains a string S.
- The last line of each test case contains a string T.

------ Output Format ------ 

For each test case, print a single line containing one integer - the maximum number of teams that Chef can form.

------ Constraints ------ 

$1 ≤ Q ≤ 1000$
$1 ≤ N ≤ 100$
$S$ and $T$ contains only characters '0' and '1'

----- Sample Input 1 ------ 
4
3
101
001
4
1010
0110
3
000
110
2
10
11

----- Sample Output 1 ------ 
1
2
0
1

----- explanation 1 ------ 
Test case $1$: The third student can team up with any other students as he knows both programming and English.

Test case $2$: The first two students make a team and the last two students make another team.

Test case $3$: No student knows how to program, hence there is no way to make a team.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Constructive algorithms

Mathematics

Ad-hoc
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
while t > 0:
	ans = 0
	n = int(input())
	p = input()
	e = input()
	(ps, es, bs, ns) = (0, 0, 0, 0)
	i = 0
	while i < n:
		if p[i] == '1' and e[i] == '0':
			ps += 1
		if e[i] == '1' and p[i] == '0':
			es += 1
		if e[i] == '1' and e[i] == p[i]:
			bs += 1
		if e[i] == '0' and e[i] == p[i]:
			ns += 1
		i += 1
	ans += min(bs, ns)
	bs = bs - ns if bs > ns else 0
	ans += min(es, ps)
	rem = abs(es - ps)
	ans += min(rem, bs)
	bs = bs - rem if bs > rem else 0
	ans += bs // 2
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	t = input()
	if n == 1 or s == '0' * n or t == '0' * n:
		print('0')
	else:
		both = eng = prog = none = 0
		for i in range(n):
			if s[i] == '1':
				if t[i] == '1':
					both += 1
				else:
					prog += 1
			elif t[i] == '1':
				eng += 1
			else:
				none += 1
		team = min(eng, prog) + min(none, both)
		if both > none:
			x = min(abs(eng - prog), both - none)
			team += x
			if both - none - x > 0:
				team += (both - none - x) // 2
		print(team)


rows = int(input())
for i in range(rows):
	n = int(input())
	p = input().count('1')
	e = input().count('1')
	print(min(p, e, int(n / 2)))


from math import floor
num_test_cases = int(input())
for _ in range(num_test_cases):
	N = int(input())
	python = list(map(int, input()))
	english = list(map(int, input()))
	both = 0
	py = 0
	eng = 0
	none = 0
	for (i, j) in zip(python, english):
		if i and j:
			both += 1
		elif i:
			py += 1
		elif j:
			eng += 1
		else:
			none += 1
	teams_with_both_none = min(both, none)
	both = both - teams_with_both_none
	teams_with_py_eng = min(py, eng)
	leftover = abs(py - eng)
	teams_with_both_py_eng = 0
	if both > 0:
		teams_with_both_py_eng = min(both, leftover)
		both -= teams_with_both_py_eng
	teams_with_both = both // 2
	teams = teams_with_py_eng + teams_with_both_none + teams_with_both_py_eng + teams_with_both
	print(teams)


def find_answer(n, english_array, programming):
	english = 0
	pro = 0
	both = 0
	nothing = 0
	for position in range(n):
		if programming[position] == '1' and english_array[position] == '1':
			both = both + 1
		elif programming[position] == '1' and english_array[position] == '0':
			pro += 1
		elif english_array[position] == '1' and programming[position] == '0':
			english += 1
		elif english_array[position] == '0' and programming[position] == '0':
			nothing += 1
	pairs_with_e_and_p = min(english, pro)
	difference = abs(english - pro) + nothing
	pairs_with_ep_and_others = min(both, difference)
	remaining_ep = both - pairs_with_ep_and_others
	pairs_with_just_ep = remaining_ep / 2
	return int(pairs_with_e_and_p + pairs_with_ep_and_others + pairs_with_just_ep)
q = int(input())
for _ in range(q):
	n = int(input())
	programming = input()
	english_array = input()
	print(find_answer(n, english_array, programming))


def test_func():
	q = int(input())
	for j in range(q):
		n = int(input())
		s = str(input())
		t = str(input())
		pro_count = 0
		weak_count = 0
		for i in range(n):
			if s[i] == '1' and t[i] == '1':
				pro_count += 1
			if s[i] == '0' and t[i] == '0':
				weak_count += 1
		s_count = s.count('1')
		t_count = t.count('1')
		s_count -= pro_count
		t_count -= pro_count
		min_t_s = min(t_count, s_count)
		total_count = min_t_s + pro_count
		if total_count >= n / 2:
			total_count = int(n / 2)
		print(total_count)
test_func()


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = c1 = c2 = 0
	for i in range(n):
		if a[i] == b[i] == '1':
			c += 1
		elif a[i] == '0' and b[i] == '1':
			c1 += 1
		elif a[i] == '1' and b[i] == '0':
			c2 += 1
	print(min(n // 2, min(c1, c2) + c))


for _ in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	d = {'11': 0, '10': 0, '01': 0, '00': 0}
	for i in range(n):
		d[s[i] + t[i]] += 1
	s1 = min(d['11'], d['00'])
	d['11'] -= s1
	s2 = min(d['01'], d['10'])
	d['01'] -= s2
	d['10'] -= s2
	s3 = min(d['11'], max(d['01'], d['10']))
	d['11'] -= s3
	print(s1 + s2 + s3 + d['11'] // 2)


for q in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	sa = sb = 0
	for i in a:
		if i == '1':
			sa += 1
	for j in b:
		if j == '1':
			sb += 1
	print(min(sa, sb, n // 2))


for _ in range(int(input())):
	n = int(input())
	coding = input()
	english = input()
	(oc, oe, bo, no) = (0, 0, 0, 0)
	for i in range(n):
		if coding[i] == '1' and english[i] == '1':
			bo += 1
		elif coding[i] == '1':
			oc += 1
		elif english[i] == '1':
			oe += 1
		else:
			no += 1
	teams = min(oc, oe) + min(bo, no)
	left1 = max(oc, oe) - min(oc, oe)
	left2 = bo - no if bo > no else 0
	teams += min(left1, left2)
	left2 = left2 - left1 if left2 > left1 else 0
	teams += left2 // 2
	print(teams)


n = int(input())
for i in range(n):
	n1 = int(input())
	n2 = int(input())
	s = 0
	while n2 > 0:
		d = n2 % 10
		if d == 1:
			s = s + 1
		n2 = n2 // 10
	n3 = int(input())
	s2 = 0
	while n3 > 0:
		d2 = n3 % 10
		if d2 == 1:
			s2 = s2 + 1
		n3 = n3 // 10
	print(min(s, s2, n1 // 2))


r = int(input())
while r > 0:
	r -= 1
	n = int(input())
	s = str(input())
	t = str(input())
	t1 = 0
	t2 = 0
	t3 = 0
	t4 = 0
	for i in range(n):
		if s[i] == '1' and t[i] == '0':
			t1 += 1
		elif s[i] == '0' and t[i] == '1':
			t2 += 1
		elif s[i] == '0' and t[i] == '0':
			t3 += 1
		else:
			t4 += 1
	if t4 == n:
		print(n // 2)
	else:
		ans = 0
		u = min(t3, t4)
		t = min(t1, t2)
		ans += u + t
		t1 -= t
		t2 -= t
		t3 -= u
		t4 -= u
		if t4 > 0:
			if t1 > 0:
				tr = min(t4, t1)
				ans += tr
				t4 -= tr
				t1 -= tr
			else:
				tr = min(t4, t2)
				ans += tr
				t4 -= tr
				t2 -= tr
		ans += t4 // 2
		print(ans)


for i in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	print(min(list(s).count('1'), list(t).count('1'), n // 2))


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	T = input()
	res = min(S.count('1'), T.count('1'), N // 2)
	print(res)


for _ in range(int(input())):
	N = int(input())
	S = input()
	T = input()
	z = 0
	zo = 0
	t = 0
	for i in range(N):
		if T[i] == '1' and S[i] == '0':
			if zo < 0:
				t += 1
			zo += 1
		elif T[i] == '0' and S[i] == '1':
			if zo > 0:
				t += 1
			zo -= 1
		elif T[i] == '0' and S[i] == '0':
			if z > 0:
				t += 1
			z -= 1
		elif T[i] == '1' and S[i] == '1':
			if z < 0:
				t += 1
			z += 1
	if z > 0:
		t += min(z, abs(zo))
		z -= min(z, abs(zo))
		t += z // 2
	print(t)


for j in range(int(input())):
	num = int(input())
	sum1 = input()
	test1 = input()
	while len(sum1) > num or len(test1) > num:
		ssum1 = input(f'Enter binary of lenght{num}')
		test1 = input(f'Enter binary of lenght{num}')
	print(min(sum1.count('1'), test1.count('1'), num // 2))


k = int(input())
while k:
	k -= 1
	n = int(input())
	s = input()
	t = input()
	s = [int(i) for i in s]
	t = [int(i) for i in t]
	(full, null, a, b) = (0, 0, 0, 0)
	for i in range(n):
		if s[i] == 1 and t[i] == 1:
			full += 1
		if s[i] == 0 and t[i] == 0:
			null += 1
		if s[i] == 1 and t[i] == 0:
			a += 1
		if s[i] == 0 and t[i] == 1:
			b += 1
	ans = 0
	if full <= null:
		ans += full
		ans += min(a, b)
	else:
		ans += null
		full -= null
		ans += min(a, b)
		a = max(a, b) - min(a, b)
		if full <= a:
			ans += full
		else:
			ans += a
			full -= a
			ans += full // 2
	print(ans)


for j in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	while len(s) > n or len(t) > n:
		s = input(f'Enter binary of lenght{n}')
		t = input(f'Enter binary of lenght{n}')
	print(min(s.count('1'), t.count('1'), n // 2))


N = int(input())
for i in range(N):
	K = int(input())
	A = str(input())
	B = str(input())
	C1 = A.count('1')
	C2 = B.count('1')
	print(min(C1, C2, K // 2))


n = int(input())
for i in range(n):
	k = int(input())
	a = str(input())
	b = str(input())
	c1 = a.count('1')
	c2 = b.count('1')
	print(min(c1, c2, k // 2))


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	T = str(input())
	s1 = s.count('1')
	s2 = T.count('1')
	print(min(s1, s2, n // 2))


for j in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	while len(s) != n or len(t) != n:
		s = input(f'Your iputed binary num was greater/lesser than {n} ,please enter a binary series of lenght{n} ')
		t = input(f'Your iputed binary num was greater/lesser than {n} ,please enter a binary series of lenght{n} ')
	print(min(s.count('1'), t.count('1'), n // 2))


for i in range(int(input())):
	n = int(input())
	p = input()
	e = input()
	pecnt = epcnt = bcnt = ncnt = 0
	for i in range(n):
		if p[i] == '1' and e[i] == '1':
			bcnt += 1
		elif p[i] == '1' and e[i] == '0':
			pecnt += 1
		elif p[i] == '0' and e[i] == '1':
			epcnt += 1
		else:
			ncnt += 1
	teams = min(pecnt, epcnt)
	teams += min(bcnt, ncnt)
	if bcnt > ncnt:
		teams += min(bcnt - ncnt, abs(pecnt - epcnt))
		if bcnt - ncnt > abs(pecnt - epcnt):
			teams += (bcnt - ncnt - abs(pecnt - epcnt)) // 2
	print(teams)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	u = str(input())
	b = s.count('1')
	c = u.count('1')
	print(min(b, c, n // 2))


for i in range(int(input())):
	import math
	N = int(input())
	S = input()
	T = input()
	cs1 = 0
	ct1 = 0
	for i in S:
		if i == '1':
			cs1 += 1
	for i in T:
		if i == '1':
			ct1 += 1
	ans = min(cs1, ct1, N // 2)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	print(min(s.count('1'), t.count('1'), n // 2))


def count(i):
	s = bin(i)
	return len(s.replace('0', '')) - 1
for _ in range(int(input())):
	n = int(input())
	s = int(input(), 2)
	t = int(input(), 2)
	both = s & t
	programming = count(s & ~both)
	english = count(t & ~both)
	both = count(both)
	print(min(n // 2, both + min(english, programming)))


for _ in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	io = 0
	oi = 0
	ii = 0
	oo = 0
	for i in range(n):
		if s[i] == '0' and t[i] == '0':
			oo += 1
		elif s[i] == '0' and t[i] == '1':
			oi += 1
		elif s[i] == '1' and t[i] == '0':
			io += 1
		else:
			ii += 1
	res = 0
	res += min(ii, oo)
	ii = max(0, ii - oo)
	diff_oi_io = abs(oi - io)
	res += min(ii, diff_oi_io)
	ii = max(0, ii - diff_oi_io)
	io = oi = min(io, oi)
	res += ii + (2 * io - ii) // 2
	print(res)


for i in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	d = {'none': 0, 'cs': 0, 'eng': 0, 'both': 0}
	for i in range(n):
		if s[i] == '1':
			if t[i] == '1':
				d['both'] += 1
			else:
				d['cs'] += 1
		elif t[i] == '1':
			d['eng'] += 1
		else:
			d['none'] += 1
	sum = 0
	if d['none'] >= d['both']:
		sum += d['both']
		d['both'] = 0
	else:
		sum += d['none']
		d['both'] -= d['none']
	if d['cs'] > d['eng']:
		sum += d['eng']
		d['cs'] -= d['eng']
		x = min(d['cs'], d['both'])
		sum += x + (d['both'] - x) // 2
	else:
		sum += d['cs']
		d['eng'] -= d['cs']
		x = min(d['eng'], d['both'])
		sum += x + (d['both'] - x) // 2
	print(sum)


q = int(input())
for j in range(q):
	ni = int(input())
	s = sum([int(si) for si in input()])
	t = sum([int(ti) for ti in input()])
	max_team = min(s, t, ni // 2)
	print(max_team)


import math
for _ in range(int(input())):
	n = int(input())
	s = input().count('1')
	t = input().count('1')
	ans = min(math.ceil(min(s, t)), n // 2)
	print(ans)


try:
	for _ in range(int(input())):
		length = int(input())
		s1 = input()
		s2 = input()
		os1 = s1.count('1')
		os2 = s2.count('1')
		print(min(os1, os2, length // 2))
except:
	pass


q = int(input())
for i in range(q):
	n = int(input())
	s = sum([int(j) for j in input()])
	t = sum([int(x) for x in input()])
	print(min(s, t, n // 2))


t = int(input())
for _ in range(t):
	s = int(input())
	p = input()
	g = input()
	mills = [0] * 4
	for i in range(s):
		mills[int(p[i] + g[i], 2)] += 1
	selfs = min(mills[3], mills[0])
	mills[3] -= selfs
	mills[0] -= selfs
	match = min(mills[1], mills[2])
	mills[1] -= match
	mills[2] -= match
	selfs += match
	for i in range(1, 3, 1):
		if mills[i] > 0 and mills[3] > 0:
			match = min(mills[i], mills[3])
			mills[3] -= match
			selfs += match
	selfs += mills[3] // 2
	print(selfs)


Q = int(input())
for _ in range(Q):
	N = int(input())
	S = input()
	T = input()
	skills = [0] * 4
	for i in range(N):
		skills[int(S[i] + T[i], 2)] += 1
	teams = min(skills[3], skills[0])
	skills[3] -= teams
	skills[0] -= teams
	match = min(skills[1], skills[2])
	skills[1] -= match
	skills[2] -= match
	teams += match
	for i in range(1, 3, 1):
		if skills[i] > 0 and skills[3] > 0:
			match = min(skills[i], skills[3])
			skills[3] -= match
			teams += match
	teams += skills[3] // 2
	print(teams)


for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = [0] * 4
	e = 0
	if len(a) == 1:
		pass
	else:
		for i in range(len(a)):
			if a[i] == '1' and b[i] == '0':
				c[0] += 1
			elif a[i] == '0' and b[i] == '1':
				c[1] += 1
			elif a[i] == '1' and b[i] == '1':
				c[2] += 1
			else:
				c[3] += 1
		d = min(c[0], c[1])
		f = abs(c[0] - c[1])
		e += d
		if f + c[3] >= c[2]:
			e += c[2]
		else:
			g = c[2] - (f + c[3])
			e += g // 2 + (f + c[3])
	print(e)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	l = [0] * 4
	for i in range(n):
		if a[i] == b[i] == '1':
			l[2] += 1
		elif a[i] == b[i] == '0':
			l[3] += 1
		elif a[i] == '0' and b[i] == '1':
			l[0] += 1
		elif a[i] == '1' and b[i] == '0':
			l[1] += 1
	ans = min(l[0], l[1])
	rem = abs(l[0] - l[1])
	if l[2] >= rem + l[3]:
		ans += rem + l[3]
		l[2] -= rem + l[3]
		ans += l[2] // 2
	else:
		ans += l[2]
	print(ans)


t = int(input())
for i in range(t):
	z = int(input())
	(x, y) = (input(), input())
	c = 0
	cx = 0
	cy = 0
	cw = 0
	for i in range(z):
		if x[i] == '1' and x[i] == y[i]:
			cw += 1
		else:
			if x[i] == '1':
				cx += 1
			if y[i] == '1':
				cy += 1
		cz = z - (cw + cx + cy)
	c += min(cx, cy) + min(cw, cz + abs(cx - cy)) + (cw - min(cw, cz + abs(cx - cy))) // 2
	print(c)


M = 1000000007

def solve():
	n = int(input())
	s = input()
	t = input()
	p = e = no = b = 0
	for i in range(n):
		if s[i] == '0' and t[i] == '0':
			no += 1
		elif s[i] == '1' and t[i] == '1':
			b += 1
		elif s[i] == '1':
			p += 1
		elif t[i] == '1':
			e += 1
	c = min(b, no) + min(p, e)
	if b > no:
		c += min(abs(p - e), b - no)
	if abs(p - e) < b - no:
		c += (b - no - abs(p - e)) // 2
	print(c)
for _ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
testcase = int(input())
while testcase:
	testcase -= 1
	n = int(input())
	r = input()
	s = input()
	ctb = 0
	ctcp = 0
	cte = 0
	for i in range(n):
		if r[i] == '1' and s[i] == '1':
			ctb += 1
		elif r[i] == '1' and s[i] == '0':
			ctcp += 1
		elif r[i] == '0' and s[i] == '1':
			cte += 1
	x = min(ctcp, cte)
	ans = ctb + min(x, (n - 2 * ctb) // 2)
	sys.stdout.write(str(ans) + '\n')


T = int(input())
for it in range(T):
	N = int(input())
	S = input()
	T = input()
	p = 0
	e = 0
	b = 0
	for i in range(N):
		if S[i] == '1' and T[i] == '0':
			p += 1
		elif S[i] == '0' and T[i] == '1':
			e += 1
		elif S[i] == '1' and T[i] == '1':
			b += 1
	s = 0
	val = min(e, p)
	s += val
	s = min(N // 2, b + val)
	print(s)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)) + '\n')

def main():
	for _ in tr():
		n = nl()
		s = line()
		t = line()
		eng_only = 0
		pro_only = 0
		both = 0
		nothing = 0
		for i in range(n):
			if s[i] == '1' and t[i] == '1':
				both += 1
			elif s[i] == '1':
				pro_only += 1
			elif t[i] == '1':
				eng_only += 1
			else:
				nothing += 1
		combo = min(eng_only, pro_only)
		result = combo
		eng_only -= combo
		pro_only -= combo
		combo = min(both, eng_only + pro_only + nothing)
		result += combo
		both -= combo
		result += both // 2
		print(result)
main()


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	(pro, eng, both, minm, rem) = (0, 0, 0, 0, 0)
	u = 0
	for i in range(n):
		if s1[i] == s2[i] == '1':
			both += 1
		elif s1[i] == '1' and s2[i] == '0':
			pro += 1
		elif s1[i] == '0' and s2[i] == '1':
			eng += 1
		else:
			rem += 1
	minm = min(pro, eng)
	pro -= minm
	eng -= minm
	u += minm
	minm = min(both, pro + rem + eng)
	u += minm
	both -= minm
	u += both // 2
	print(u)


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	T = input()
	no = 0
	oe = 0
	op = 0
	bo = 0
	res = 0
	for i in range(N):
		if S[i] == '1' and T[i] == '1':
			bo += 1
		elif S[i] == '1':
			op += 1
		elif T[i] == '1':
			oe += 1
		else:
			no += 1
	if oe > op:
		oe = oe - op
		res += op
		if bo > no:
			bo = bo - no
			res += no
			if bo > oe:
				bo = bo - oe
				res += oe
				res += bo // 2
			else:
				res += bo
		else:
			res += bo
	else:
		op = op - oe
		res += oe
		if bo > no:
			bo = bo - no
			res += no
			if bo > op:
				bo = bo - op
				res += op
				res += bo // 2
			else:
				res += bo
		else:
			res += bo
	print(res)


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	o1 = []
	o2 = []
	t2 = []
	t4 = []
	for i in range(n):
		if s1[i] == '1' and s2[i] == '0':
			o1.append(1)
		elif s2[i] == '1' and s1[i] == '0':
			o2.append(1)
		elif s1[i] == '1' and s2[i] == '1':
			t2.append(1)
		else:
			t4.append(1)
	max_team = n // 2
	mn = min(len(o1), len(o2))
	if mn < max_team:
		while len(t2) > 0 and mn < max_team:
			mn += t2.pop(0)
	print(mn)


for k in range(int(input())):
	a12 = int(input())
	b12 = input()
	c12 = input()
	d12 = {'none': 0, 'cs': 0, 'eng': 0, 'both': 0}
	for k in range(a12):
		if b12[k] == '1':
			if c12[k] == '1':
				d12['both'] += 1
			else:
				d12['cs'] += 1
		elif c12[k] == '1':
			d12['eng'] += 1
		else:
			d12['none'] += 1
	sum = 0
	if d12['none'] >= d12['both']:
		sum += d12['both']
		d12['both'] = 0
	else:
		sum += d12['none']
		d12['both'] -= d12['none']
	if d12['cs'] > d12['eng']:
		sum += d12['eng']
		d12['cs'] -= d12['eng']
		e34 = min(d12['cs'], d12['both'])
		sum += e34 + (d12['both'] - e34) // 2
	else:
		sum += d12['cs']
		d12['eng'] -= d12['cs']
		e34 = min(d12['eng'], d12['both'])
		sum += e34 + (d12['both'] - e34) // 2
	print(sum)