Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef and his friend Magda have $2N$ mutual friends: $N$ of these friends are chefs and the other $N$ are chefettes. The chefs are numbered $1$ through $N$ and the chefettes are (independently) also numbered $1$ through $N$. Since Magda wants their friends to be as happy as possible and to preserve traditional family values, she wants to pair them up in such a way that each chef is paired with exactly one chefette and each chefette with exactly one chef.

The chefs have heights $A_{1}, A_{2}, \ldots, A_{N}$ and the chefettes have heights $B_{1}, B_{2}, \ldots, B_{N}$. For each valid $i, j$, if the $i$-th chef and the $j$-th chefette are paired, they will have exactly one child with height $\lfloor\frac{A_{i}+B_{j}}{2}\rfloor$. Magda wants to pair up the chefs and chefettes in such a way that the sum of heights of all their children ($N$ children in total) is maximum possible. Please help her do that.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
The third line contains $N$ space-separated integers $B_{1}, B_{2}, \ldots, B_{N}$.

------  Output ------
Print a single line containing one integer ― the maximum sum of heights of the children.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ B_{i} ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (40 points): $1 ≤ N ≤ 100$

Subtask #2 (60 points): original constraints

----- Sample Input 1 ------ 
2
3
4 5 6
1 2 3
5
4 8 6 4 1
2 5 7 4 7
----- Sample Output 1 ------ 
10
23
----- explanation 1 ------ 
Example case 1: One possible solution is to pair the first chef with the second chefette, the second chef with the first chefette and the third chef with the third chefette. Their children will have heights $3$, $3$ and $4$, respectively.

Difficulty: MEDIUM
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	oa = []
	ea = []
	ob = []
	eb = []
	for i in range(n):
		if a[i] % 2:
			oa.append(a[i])
		else:
			ea.append(a[i])
		if b[i] % 2:
			ob.append(b[i])
		else:
			eb.append(b[i])
	oa.sort()
	ea.sort()
	ob.sort()
	eb.sort()
	new_a = oa + ea
	new_b = ob + eb
	ans = 0
	for i in range(n):
		ans += (new_a[i] + new_b[i]) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	t = (sum(x) + sum(y)) / 2
	even = 0
	for i in list(x):
		if i % 2 == 0:
			even += 1
	for i in list(y):
		if i % 2 == 0:
			even -= 1
	print(int(t - 0.5 * abs(even)))


for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	(sum, oddA, oddB) = (0, 0, 0)
	for i in range(N):
		if A[i] % 2:
			oddA += 1
		if B[i] % 2:
			oddB += 1
		sum += (A[i] + B[i]) / 2
	print(int(sum - 0.5 * (oddA - oddB if oddA > oddB else oddB - oddA)))


t = int(input())
for _ in range(t):
	n = int(input())
	c1 = list(map(int, input().split()))
	c2 = list(map(int, input().split()))
	ec1 = []
	ec2 = []
	oc1 = []
	oc2 = []
	for i in range(n):
		cc1 = c1[i]
		cc2 = c2[i]
		if cc1 % 2 == 0:
			ec1.append(cc1)
		else:
			oc1.append(cc1)
		if cc2 % 2 == 0:
			ec2.append(cc2)
		else:
			oc2.append(cc2)
	c1 = ec1 + oc1
	c2 = ec2 + oc2
	vl = 0
	for i in range(n):
		vl += (c1[i] + c2[i]) // 2
	print(vl)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s1 = sum(a)
	s2 = sum(b)
	a_even = 0
	b_even = 0
	for i in range(n):
		if a[i] % 2 == 0:
			a_even += 1
		if b[i] % 2 == 0:
			b_even += 1
	diff = abs(a_even - b_even)
	ans = (s1 + s2 - diff) // 2
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = []
	q = []
	k = []
	l = []
	s = 0
	for i in a:
		if i % 2 == 0:
			p += [i]
		else:
			q += [i]
	for i in b:
		if i % 2 == 0:
			if p != []:
				s += (i + p.pop()) // 2
			else:
				k += [i]
		elif q != []:
			s += (i + q.pop()) // 2
		else:
			l += [i]
	while p != [] and k != []:
		i = p.pop()
		j = k.pop()
		s += (i + j) // 2
	while p != [] and l != []:
		i = p.pop()
		j = l.pop()
		s += (i + j) // 2
	while q != [] and k != []:
		i = q.pop()
		j = k.pop()
		s += (i + j) // 2
	while q != [] and l != []:
		i = q.pop()
		j = l.pop()
		s += (i + j) // 2
	print(s)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	evena = 0
	evenb = 0
	for i in a:
		if i % 2 == 0:
			evena += 1
	for i in b:
		if i % 2 == 0:
			evenb += 1
	print((sum(a) + sum(b) - abs(evenb - evena)) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	even_A = 0
	even_B = 0
	for a in A:
		if a % 2 == 0:
			even_A = even_A + 1
	for b in B:
		if b % 2 == 0:
			even_B = even_B + 1
	print((sum(A) + sum(B) - abs(even_A - even_B)) // 2)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	oa = list(filter(lambda x: x % 2 != 0, a))
	oal = len(oa)
	ob = list(filter(lambda x: x % 2 != 0, b))
	obl = len(ob)
	s = (sum(a) + sum(b)) / 2
	s = s - 0.5 * abs(obl - oal)
	print(int(s))
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	odda = []
	oddb = []
	evena = []
	evenb = []
	for i in range(n):
		if a[i] % 2 == 0:
			evena.append(a[i])
		if a[i] % 2 == 1:
			odda.append(a[i])
		if b[i] % 2 == 0:
			evenb.append(b[i])
		if b[i] % 2 == 1:
			oddb.append(b[i])
	evena = evena + odda
	evenb = evenb + oddb
	sum = 0
	for i in range(n):
		x = (evena[i] + evenb[i]) // 2
		sum += x
	print(sum)


def main():
	t = int(input())
	for iteration in range(t):
		n = int(input())
		(em, ef) = (0, 0)
		a = [int(x) for x in input().split()]
		b = [int(x) for x in input().split()]
		for i in range(n):
			em += int(not a[i] % 2)
			ef += int(not b[i] % 2)
		print((sum(a) + sum(b) - abs(em - ef)) // 2)
main()


a = int(input())
for i in range(a):
	N = int(input())
	array1 = list(map(int, input().split()))
	array2 = list(map(int, input().split()))
	odd1 = 0
	odd2 = 0
	sum = 0
	for k in array1:
		sum += k
		if k % 2 != 0:
			odd1 += 1
	for k in array2:
		sum += k
		if k % 2 != 0:
			odd2 += 1
	diff = abs(odd1 - odd2)
	sum -= diff
	print(int(sum / 2))


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, a, b) = (IN(), I(), I())
	(c, d, e, f, r, s) = (0, 0, 0, 0, 0, 0)
	for i in a:
		s += i
		if i & 1:
			c += 1
		else:
			d += 1
	for i in b:
		s += i
		if i & 1:
			e += 1
		else:
			f += 1
	t = n - min(c, e) - min(d, f)
	print((s - t) // 2)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	an1 = 0
	an2 = 0
	for (i, j) in zip(l1, l2):
		if i % 2 == 0:
			an1 += 1
		if j % 2 == 0:
			an1 -= 1
		an2 += i + j
	print((an2 - abs(an1)) // 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	o = [i for i in a if i % 2 == 1]
	e = [i for i in a if i % 2 == 0]
	o1 = [i for i in b if i % 2 == 1]
	o2 = [i for i in b if i % 2 == 0]
	a = o + e
	b = o1 + o2
	ans = 0
	for (i, j) in zip(a, b):
		ans += (i + j) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a1 = [int(x) for x in input().split()]
	b1 = [int(x) for x in input().split()]
	answer = sum(a1) + sum(b1)
	diff = abs(len(list(filter(lambda x: x % 2 == 0, a1))) - len(list(filter(lambda x: x % 2 == 0, b1))))
	fin = answer // 2 - diff // 2
	print(fin)


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = list(map(int, input().split()))
	list2 = list(map(int, input().split()))
	total_sum = 0
	a = 0
	b = 0
	for i in range(n):
		total_sum = total_sum + list1[i] + list2[i]
		if list1[i] % 2 == 1:
			a = a + 1
		if list2[i] % 2 == 1:
			b = b + 1
	if a != b:
		total_sum = total_sum - abs(a - b)
	total_sum = total_sum // 2
	print(total_sum)


for _ in range(int(input())):
	n = int(input())
	lis1 = sorted(list(map(int, input().split())), key=lambda x: x % 2 == 0)
	lis2 = sorted(list(map(int, input().split())), key=lambda x: x % 2 == 0)
	print(sum(list(map(lambda a, b: (a + b) // 2, lis1, lis2))))


for z in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	val = a = b = 0
	for i in range(n):
		if A[i] % 2 == 1:
			a += 1
		if B[i] % 2 == 1:
			b += 1
		val += A[i] // 2 + B[i] // 2
	val += min(a, b)
	print(val)


T = int(input())
for x in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ea = eb = oa = ob = 0
	for i in range(n):
		if a[i] % 2 == 0:
			ea += 1
		else:
			oa += 1
		if b[i] % 2 == 0:
			eb += 1
		else:
			ob += 1
	r = (sum(a) + sum(b)) // 2 - (n - min(ea, eb) - min(oa, ob)) // 2
	print(r)


from sys import stdin
stdint = lambda : int(stdin.readline())
seq = lambda : list(map(int, stdin.readline().strip().split()))
for _ in range(stdint()):
	n = stdint()
	a = seq()
	b = seq()
	evenA = evenB = oddA = oddB = 0
	for i in range(n):
		if a[i] % 2 == 0:
			evenA += 1
		else:
			oddA += 1
		if b[i] % 2 == 0:
			evenB += 1
		else:
			oddB += 1
	res = (sum(a) + sum(b)) // 2 - (n - min(evenA, evenB) - min(oddA, oddB)) // 2
	print(res)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	even_A = even_B = odd_A = odd_B = 0
	for i in range(n):
		if A[i] % 2 == 0:
			even_A += 1
		if A[i] % 2 != 0:
			odd_A += 1
		if B[i] % 2 == 0:
			even_B += 1
		if B[i] % 2 != 0:
			odd_B += 1
	res = (sum(A) + sum(B)) / 2 - (n - min(even_A, even_B) - min(odd_A, odd_B)) / 2
	print(int(res))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ea = 0
	oa = 0
	eb = 0
	ob = 0
	for i in range(n):
		if a[i] % 2 == 0:
			ea += 1
		elif a[i] % 2 != 0:
			oa += 1
		if b[i] % 2 == 0:
			eb += 1
		elif b[i] % 2 != 0:
			ob += 1
	m = n - (min(ea, eb) + min(ob, oa))
	res = sum(a) + sum(b) - m
	print(res // 2)
	t -= 1


for q in range(int(input())):
	n = int(input())
	(evena, odda, evenb, oddb) = ([], [], [], [])
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	for i in a:
		if i % 2:
			odda.append(i)
		else:
			evena.append(i)
	for i in b:
		if i % 2:
			oddb.append(i)
		else:
			evenb.append(i)
	ans = 0
	while oddb and odda:
		ans += (odda.pop() + oddb.pop()) // 2
	while evena and evenb:
		ans += evena.pop() // 2 + evenb.pop() // 2
	while odda and evenb:
		ans += (odda.pop() + evenb.pop()) // 2
	while oddb and evena:
		ans += (oddb.pop() + evena.pop()) // 2
	print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	s1 = input().split()
	s2 = input().split()
	arr1 = [int(x) for x in s1]
	arr2 = [int(x) for x in s2]
	odd1 = 0
	odd2 = 0
	even1 = 0
	even2 = 0
	sum1 = 0
	sum2 = 0
	for el in arr1:
		if el % 2 == 0:
			even1 += 1
		else:
			odd1 += 1
		sum1 += el
	for el in arr2:
		if el % 2 == 0:
			even2 += 1
		else:
			odd2 += 1
		sum2 += el
	good_pair = min(odd1, odd2) + min(even1, even2)
	poor_pair = n - good_pair
	ans = (sum1 + sum2 - poor_pair) // 2
	print(ans)


case = int(input())
for i in range(case):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	odda = 0
	suma = 0
	for value in a:
		suma += value
		if value % 2 != 0:
			odda += 1
	oddb = 0
	sumb = 0
	for value in b:
		sumb += value
		if value % 2 != 0:
			oddb += 1
	odd = abs(odda - oddb)
	res = (suma + sumb) / 2
	res -= odd * 0.5
	print(int(res))


z = int(input())
for j in range(0, z):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	c1 = 0
	c2 = 0
	sum1 = 0
	sum2 = 0
	for i in range(n):
		sum1 += l1[i]
		sum2 += l2[i]
		if l1[i] % 2 == 1:
			c1 += 1
		if l2[i] % 2 == 1:
			c2 += 1
	sum = sum1 + sum2 - abs(c1 - c2)
	print(int(sum / 2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	ae = []
	ao = []
	be = []
	bo = []
	for i in a:
		if i % 2 == 0:
			ae.append(i)
		else:
			ao.append(i)
	for i in b:
		if i % 2 == 0:
			be.append(i)
		else:
			bo.append(i)
	ae.extend(ao)
	be.extend(bo)
	ans = 0
	for i in range(n):
		ans += (ae[i] + be[i]) // 2
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	oddCountA = 0
	oddCountB = 0
	totalSum = sum(A) + sum(B)
	totalSum //= 2
	for x in A:
		if x % 2:
			oddCountA += 1
	for x in B:
		if x % 2:
			oddCountB += 1
	totalSum -= abs(oddCountB - oddCountA) // 2
	print(totalSum)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	(oa, ob) = (0, 0)
	res = 0
	for i in range(N):
		res += A[i] + B[i]
		if A[i] % 2:
			oa += 1
		if B[i] % 2:
			ob += 1
	print(res // 2 - abs(oa - ob) // 2)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	(evens, odds) = ([], [])
	for n in B:
		if n % 2 == 0:
			evens.append(n)
		else:
			odds.append(n)
	res = 0
	for n in A:
		if n % 2 == 0:
			if evens:
				res += (evens.pop() + n) // 2
			else:
				res += (odds.pop() + n) // 2
		elif odds:
			res += (odds.pop() + n) // 2
		else:
			res += (evens.pop() + n) // 2
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	even_a = []
	even_b = []
	odd_a = []
	odd_b = []
	for ind in range(n):
		if a[ind] % 2 == 0:
			even_a.append(a[ind])
		else:
			odd_a.append(a[ind])
		if b[ind] % 2 == 0:
			even_b.append(b[ind])
		else:
			odd_b.append(b[ind])
	a = even_a + odd_a
	b = even_b + odd_b
	sum = 0
	for ind in range(n):
		avg = (a[ind] + b[ind]) // 2
		sum += avg
	print(sum)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	odd = []
	even = []
	for x in b:
		if x & 1:
			odd.append(x)
		else:
			even.append(x)
	oi = 0
	ei = 0
	ans = 0
	for x in a:
		if x & 1:
			if oi < len(odd):
				ans += (odd[oi] + x) // 2
				oi += 1
			else:
				ans += (even[ei] + x) // 2
				ei += 1
		elif ei < len(even):
			ans += (even[ei] + x) // 2
			ei += 1
		else:
			ans += (odd[oi] + x) // 2
			oi += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	b = [int(j) for j in input().split(' ')]
	(odda, oddb) = (0, 0)
	for i in range(n):
		if a[i] % 2:
			odda += 1
		if b[i] % 2:
			oddb += 1
	print((sum(a) + sum(b)) // 2 - abs(odda - oddb) // 2)


for i in range(int(input())):
	nd = int(input())
	ad = list(map(int, input().split()))
	bd = list(map(int, input().split()))
	ced = 0
	cbd = 0
	sd = 0
	for i in range(nd):
		if ad[i] % 2 == 0:
			ced += 1
		if bd[i] % 2 == 0:
			cbd += 1
		sd += ad[i] + bd[i]
	print((sd - abs(ced - cbd)) // 2)


for i in range(int(input())):
	n = int(input())
	s1 = input().split(' ')
	s2 = input().split(' ')
	(s1e, s1o, s2e, s2o) = (0, 0, 0, 0)
	c = 0
	for i in s1:
		if int(i) % 2 == 0:
			s1e += 1
		else:
			s1o += 1
		c += int(i)
	for i in s2:
		if int(i) % 2 == 0:
			s2e += 1
		else:
			s2o += 1
		c += int(i)
	k1 = abs(s1e - s2e)
	print(int(c / 2 - k1 / 2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = 0
	y = 0
	s = 0
	for i in range(n):
		if a[i] % 2 == 0:
			x += 1
		if b[i] % 2 == 0:
			y += 1
		s += a[i] + b[i]
	print((s - abs(x - y)) // 2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	cea = 0
	ceb = 0
	s = 0
	for i in range(n):
		if a[i] % 2 == 0:
			cea += 1
		if b[i] % 2 == 0:
			ceb += 1
		s += a[i] + b[i]
	print((s - abs(cea - ceb)) // 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = [i for i in a if i & 1 == 0] + [i for i in a if i & 1 == 1]
	b = [i for i in b if i & 1 == 0] + [i for i in b if i & 1 == 1]
	print(sum(((a[x] + b[x]) // 2 for x in range(n))))


tests = int(input())
for i in range(tests):
	length = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a_odd = []
	b_odd = []
	a_even = []
	b_even = []
	for j in range(length):
		if a[j] % 2 == 0:
			a_even.append(a[j])
		else:
			a_odd.append(a[j])
		if b[j] % 2 == 0:
			b_even.append(b[j])
		else:
			b_odd.append(b[j])
	a = a_even + a_odd
	b = b_even + b_odd
	ans = 0
	for j in range(length):
		ans += (a[j] + b[j]) // 2
	print(ans)


from functools import cmp_to_key
tests = int(input())

def sort_even_and_odd(a, b):
	if a % 2:
		return 1
	return -1
for i in range(tests):
	length = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = sorted(a, key=cmp_to_key(sort_even_and_odd))
	b = sorted(b, key=cmp_to_key(sort_even_and_odd))
	ans = 0
	for j in range(length):
		ans += (a[j] + b[j]) // 2
	print(ans)


import queue
T = int(input())
while T > 0:
	n = int(input())
	b = [int(i) for i in input().split()]
	g = [int(i) for i in input().split()]
	x = [i % 2 for i in b]
	y = [i % 2 for i in g]
	print((sum(g) + sum(b)) // 2 - abs(x.count(1) - y.count(1)) // 2)
	T -= 1


for _ in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().split()]
	B = [int(i) for i in input().split()]
	a = [i % 2 for i in A]
	b = [i % 2 for i in B]
	x = (sum(A) + sum(B)) // 2
	y = abs(a.count(1) - b.count(1)) // 2
	print(x - y)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	oa = 0
	ob = 0
	s = 0
	for j in a:
		if j % 2 == 1:
			oa += 1
		s = s + j
	for k in b:
		if k % 2 == 1:
			ob += 1
		s = s + k
	print(int(s / 2 - abs(oa - ob) / 2))


for _ in range(int(input())):
	n = int(input())
	Ai = list(map(int, input().split()))
	Bi = list(map(int, input().split()))
	evencounta = 0
	evencountb = 0
	oddcounta = 0
	oddcountb = 0
	sume = 0
	for i in range(n):
		if Ai[i] % 2 == 0:
			evencounta += 1
		elif Ai[i] % 2:
			oddcounta += 1
		if Bi[i] % 2 == 0:
			evencountb += 1
		elif Bi[i] % 2:
			oddcountb += 1
		if Ai[i] % 2 == 0 and Bi[i] % 2 == 0:
			evencounta -= 1
			evencountb -= 1
		elif Ai[i] % 2 and Bi[i] % 2:
			oddcounta -= 1
			oddcountb -= 1
		sume += (Ai[i] + Bi[i]) // 2
	ans = sume + (min(evencounta, evencountb) + min(oddcountb, oddcounta)) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = 0
	(o1, o2) = (0, 0)
	for i in range(n):
		if a[i] % 2:
			o1 += 1
		if b[i] % 2:
			o2 += 1
	x = min(o1, o2) + min(n - o1, n - o2)
	print((sum(a) + sum(b) - n + x) // 2)


for tests in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l1e = list(filter(lambda x: x % 2 == 0, l1))
	l1o = list(filter(lambda x: x % 2 != 0, l1))
	l2e = list(filter(lambda x: x % 2 == 0, l2))
	l2o = list(filter(lambda x: x % 2 != 0, l2))
	l1e.sort()
	l1o.sort()
	l2e.sort()
	l2o.sort()
	l1 = l1e + l1o
	l2 = l2e + l2o
	sum = 0
	for i in range(n):
		sum += int((l1[i] + l2[i]) / 2)
	print(sum)


def solve():
	n = int(input())
	al = sorted(map(int, input().split()))
	bl = sorted(map(int, input().split()))
	tot = 0
	(ao, ae, bo, be) = ([], [], [], [])
	for i in range(n):
		if (al[i] + bl[i]) % 2 == 0:
			tot += (al[i] + bl[i]) // 2
		else:
			if al[i] % 2:
				ao.append(al[i])
			else:
				ae.append(al[i])
			if bl[i] % 2:
				bo.append(bl[i])
			else:
				be.append(bl[i])
	while len(ao) > 0 and len(bo) > 0:
		tot += (ao.pop() + bo.pop()) // 2
	while len(ae) > 0 and len(be) > 0:
		tot += (ae.pop() + be.pop()) // 2
	if len(ao) > 0:
		while len(ao) > 0 and len(be) > 0:
			tot += (ao.pop() + be.pop()) // 2
	elif len(bo) > 0:
		while len(bo) > 0 and len(ae) > 0:
			tot += (ae.pop() + bo.pop()) // 2
	if len(ae) > 0:
		while len(ae) > 0 and len(bo) > 0:
			tot += (ae.pop() + bo.pop()) // 2
	elif len(be) > 0:
		while len(be) > 0 and len(ao) > 0:
			tot += (ao.pop() + be.pop()) // 2
	print(tot)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	d = 0
	ans = sum(a) + sum(b)
	for i in a:
		if i % 2 == 0:
			c += 1
	for i in b:
		if i % 2 == 0:
			d += 1
	print((ans - abs(c - d)) // 2)


T = int(input())
for i in range(0, T):
	a = int(input())
	cf = input().split()
	cn = input().split()
	for j in range(0, a):
		cf[j] = int(cf[j])
		cn[j] = int(cn[j])
	cc = 0
	ca = 0
	sums = 0
	for j in range(0, a):
		cf[j] = int(cf[j])
		cn[j] = int(cn[j])
		sums += cn[j] + cf[j]
	for j in cf:
		if j % 2 == 0:
			cc += 1
	for j in cn:
		if j % 2 == 0:
			ca += 1
	cc = abs(cc - ca)
	print((sums - cc) // 2)


for _ in range(int(input())):
	n = int(input())
	chefs = list(map(int, input().split()))
	cheffetes = list(map(int, input().split()))
	even_chefs = 0
	even_cheffetes = 0
	for i in range(n):
		if chefs[i] % 2 == 0:
			even_chefs += 1
		if cheffetes[i] % 2 == 0:
			even_cheffetes += 1
	diff = abs(even_cheffetes - even_chefs)
	print((sum(chefs) + sum(cheffetes) - diff) // 2)


for i in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	count1 = 0
	count2 = 0
	s = 0
	for i in range(n):
		if l1[i] % 2 != 0:
			count1 += 1
		if l2[i] % 2 != 0:
			count2 += 1
		s = s + l1[i] + l2[i]
	d = abs(count1 - count2)
	print((s - d) // 2)


test = int(input())
for i in range(test):
	arr = int(input())
	lis1 = list(map(int, input().split()))
	lis2 = list(map(int, input().split()))
	odd1 = 0
	even1 = 0
	odd2 = 0
	even2 = 0
	for j in lis1:
		if j % 2 != 0:
			odd1 += 1
		elif j % 2 == 0:
			even1 += 1
	for k in lis2:
		if k % 2 != 0:
			odd2 += 1
		elif k % 2 == 0:
			even2 += 1
	oddevenpairs = (abs(odd1 - odd2) + abs(even1 - even2)) // 2
	print((sum(lis1) + sum(lis2) - oddevenpairs) // 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ae = []
	ao = []
	for i in a:
		if i % 2 == 0:
			ae.append(i)
		else:
			ao.append(i)
	be = []
	bo = []
	for i in b:
		if i % 2 == 0:
			be.append(i)
		else:
			bo.append(i)
	ae.sort(reverse=True)
	ao.sort(reverse=True)
	be.sort(reverse=True)
	bo.sort(reverse=True)
	p = min(len(ae), len(be))
	p1 = min(len(ao), len(bo))
	ae1 = ae[:p]
	be1 = be[:p]
	ao1 = ao[:p1]
	bo1 = bo[:p1]
	se = (sum(ae1) + sum(be1) + sum(ao1) + sum(bo1)) // 2
	ae2 = ae[p:]
	be2 = be[p:]
	ao2 = ao[p1:]
	bo2 = bo[p1:]
	if len(ae2) == 0:
		c = be2
	else:
		c = ae2
	if len(ao2) == 0:
		d = bo2
	else:
		d = ao2
	so = 0
	for i in range(len(d)):
		so += (c[i] + d[i]) // 2
	print(se + so)


from math import *
t = int(input())
for tt in range(t):
	n = int(input())
	boys = [int(i) for i in input().split()]
	girls = [int(i) for i in input().split()]
	(e1, e2) = (0, 0)
	sum1 = 0
	for i in boys:
		sum1 = sum1 + i
		if i % 2 == 0:
			e1 = e1 + 1
	for i in girls:
		sum1 = sum1 + i
		if i % 2 == 0:
			e2 = e2 + 1
	less = abs(e1 - e2) / 2
	print(int(sum1 / 2 - less))


import math
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	sum1 = 0
	odd = 0
	for j in x:
		sum1 += j
		if j & 1:
			odd += 1
	for j in y:
		sum1 += j
		if j & 1:
			odd -= 1
	print((sum1 - abs(odd)) // 2)


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	count1 = 0
	count2 = 0
	for i in arr1:
		if i % 2 == 1:
			count1 += 1
	for i in arr2:
		if i % 2 == 1:
			count2 += 1
	diff = abs(count1 - count2)
	summ = sum(arr1) + sum(arr2)
	req = summ - diff
	print(int(req / 2))


import math
for i in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	(c1, c2) = (0, 0)
	for i in range(n):
		if l1[i] % 2 != 0:
			c1 += 1
		if l2[i] % 2 != 0:
			c2 += 1
	val = abs(c1 - c2)
	print(math.ceil((sum(l1) + sum(l2)) / 2) - math.ceil(val / 2))


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	ip = input().split()
	a = [int(x) for x in ip]
	ip = input().split()
	b = [int(x) for x in ip]
	oa = []
	ea = []
	ob = []
	eb = []
	for x in a:
		if x % 2 == 0:
			ea.append(x)
		else:
			oa.append(x)
	for x in b:
		if x % 2 == 0:
			eb.append(x)
		else:
			ob.append(x)
	xa = ea + oa
	xb = eb + ob
	s = 0
	for i in range(n):
		s += math.floor((xa[i] + xb[i]) // 2)
	print(s)


t = int(input())
for i in range(t):
	n1 = int(input())
	c = list(map(int, input().split()))
	c1 = list(map(int, input().split()))
	odd1 = 0
	sum1 = 0
	for i in c:
		sum1 += i
		if i % 2 != 0:
			odd1 += 1
	for j in c1:
		sum1 += j
		if j % 2 != 0:
			odd1 -= 1
	t = (sum1 - abs(odd1)) // 2
	print(t)