Chefina has two sequences $A_1, A_2, \ldots, A_N$ and $B_1, B_2, \ldots, B_N$. She views two sequences with length $N$ as identical if, after they are sorted in non-decreasing order, the $i$-th element of one sequence is equal to the $i$-th element of the other sequence for each $i$ ($1 \le i \le N$).
To impress Chefina, Chef wants to make the sequences identical. He may perform the following operation zero or more times: choose two integers $i$ and $j$ $(1 \le i,j \le N)$ and swap $A_i$ with $B_j$. The cost of each such operation is $\mathrm{min}(A_i, B_j)$.
You have to find the minimum total cost with which Chef can make the two sequences identical.

-----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-----
For each test case, print a single line containing one integer ― the minimum cost, or $-1$ if no valid sequence of operations exists.

-----Constraints-----
- $1 \le T \le 2,000$
- $1 \le N \le 2 \cdot 10^5$
- $1 \le A_i, B_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^6$

-----Subtasks-----
Subtask #1 (15 points):
- $T \le 20$
- $N \le 20$
Subtask #2 (85 points): original constraints

-----Example Input-----
3
1
1
2
2
1 2
2 1
2
1 1
2 2

-----Example Output-----
-1
0
1

-----Explanation-----
Example case 1: There is no way to make the sequences identical, so the answer is $-1$.
Example case 2: The sequence are identical initially, so the answer is $0$.
Example case 3: We can swap $A_1$ with $B_2$, which makes the two sequences identical, so the answer is $1$.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from collections import Counter
tc = int(input())
for k in range(tc):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	b = list(map(int, input().rstrip().split()))
	cc = sorted(a + b)
	p = []
	q = []
	for i in range(0, 2 * n, 2):
		p.append(cc[i])
	for i in range(1, 2 * n + 1, 2):
		q.append(cc[i])
	if p != q:
		print('-1')
		continue
	a.sort()
	b.sort()
	if a == b:
		print('0')
		continue
	xx = list((Counter(a) - Counter(p)).elements())
	yy = list((Counter(b) - Counter(p)).elements())
	iu = len(xx)
	gb = sorted(xx + yy)
	uu = xx[0]
	vv = yy[0]
	zz = min(cc[0], uu, vv)
	ans = 0
	for i in range(iu):
		if gb[i] <= zz * 2:
			ans += gb[i]
		else:
			ans += zz * 2
	print(ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	x = sorted(map(int, input().split()))
	y = sorted(map(int, input().split()))
	a = Counter(x)
	b = Counter(y)
	c = a + b
	l = []
	mini = min(x[0], y[0])
	for i in c.keys():
		if c[i] % 2 == 1:
			print(-1)
			break
		else:
			l.extend([i] * (abs(a[i] - b[i]) // 2))
	else:
		l.sort()
		cost = 0
		for i in range(len(l) // 2):
			cost = cost + min(l[i], 2 * mini)
		print(cost)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	b = sorted(map(int, input().split()))
	x = Counter(a)
	y = Counter(b)
	z = x + y
	l = []
	q = min(a[0], b[0])
	for k in list(z.keys()):
		if z[k] % 2 == 1:
			print(-1)
			break
		else:
			l.extend([k] * (abs(x[k] - y[k]) // 2))
	else:
		l.sort()
		ans = 0
		if l == []:
			print(0)
		else:
			for i in range(len(l) // 2):
				ans += min(l[i], 2 * q)
			print(ans)


def chef_cost(A, B, n):
	checksum = 0
	mn1 = min(A)
	mn2 = min(B)
	mn = min(mn1, mn2)
	mpa = {}
	for i in range(n):
		checksum ^= A[i]
		if A[i] not in mpa:
			mpa[A[i]] = 1
		else:
			mpa[A[i]] += 1
	mpb = {}
	for i in range(n):
		checksum ^= B[i]
		if B[i] not in mpb:
			mpb[B[i]] = 1
		else:
			mpb[B[i]] += 1
	if checksum:
		return -1
	for i in mpa:
		if i in mpb:
			dx = min(mpa[i], mpb[i])
			mpa[i] -= dx
			mpb[i] -= dx
	a1 = []
	b1 = []
	for i in mpa:
		for j in range(mpa[i] // 2):
			a1.append(i)
	for i in mpb:
		for j in range(mpb[i] // 2):
			b1.append(i)
	a1.sort()
	b1.sort(reverse=True)
	cost = 0
	for i in range(len(a1)):
		cost += min(2 * mn, min(a1[i], b1[i]))
	return cost
test = int(input())
for _ in range(test):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print(chef_cost(A, B, n))


for i in range(int(input())):
	n = int(input())
	a = []
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	m = 10 ** 6
	arr = [0] * (10 ** 6 + 1)
	for i in range(n):
		arr[a[i]] += 1
		arr[b[i]] += 1
		m = min(m, a[i], b[i])
	f = 0
	for i in range(len(arr)):
		if arr[i] % 2 != 0:
			f = -1
			break
		else:
			arr[i] = arr[i] // 2
	(a1, b1) = ([], [])
	bn = arr.copy()
	an = arr.copy()
	for i in range(n):
		if an[a[i]]:
			an[a[i]] -= 1
		else:
			a1.append(a[i])
	for i in range(n):
		if bn[b[i]]:
			bn[b[i]] -= 1
		else:
			b1.append(b[i])
	a1.sort()
	b1.sort(reverse=True)
	if len(a1) != len(b1):
		f = -1
	if f == -1:
		print(-1)
	else:
		count = 0
		for i in range(len(a1)):
			count += min(2 * m, a1[i], b1[i])
		print(count)


t = int(input())
while t > 0:
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	(resultant, s) = ([], set())
	for i in range(0, len(arr1)):
		s.add(arr1[i])
		resultant.append(arr1[i])
	for i in range(0, len(arr2)):
		s.add(arr2[i])
		resultant.append(arr2[i])
	checker = 0
	for i in resultant:
		if resultant.count(i) % 2 == 1:
			checker = 1
			print(-1)
			break
	if checker == 0:
		vector = []
		for i in s:
			temp = resultant.count(i) / 2
			if temp < arr1.count(i):
				while arr1.count(i) - temp:
					vector.append(i)
					temp += 1
			elif temp < arr2.count(i):
				while arr2.count(i) - temp:
					vector.append(i)
					temp += 1
		vector.sort()
		mini = 2 * min(min(arr1), min(arr2))
		ans = 0
		for i in range(0, len(vector) // 2):
			ans += min(mini, vector[i])
		print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	min_a = min(a)
	min_b = min(b)
	m = min(min_a, min_b)
	da = {}
	for item in a:
		if item in da:
			da[item] += 1
		else:
			da[item] = 1
	for item in b:
		if item in da:
			da[item] += 1
		else:
			da[item] = 1
	correct = {}
	pos = 1
	for (key, value) in list(da.items()):
		if value % 2:
			pos = 0
			break
		else:
			correct[key] = value // 2
	if pos == 0:
		print(-1)
		continue
	ref = correct.copy()
	var1 = []
	var2 = []
	for i in range(0, n):
		if ref[a[i]]:
			ref[a[i]] -= 1
		else:
			var1.append(a[i])
	ref = correct.copy()
	for i in range(0, n):
		if ref[b[i]]:
			ref[b[i]] -= 1
		else:
			var2.append(b[i])
	if len(var1) == 0:
		print(0)
		continue
	if len(var1) != len(var2):
		print(-1)
		continue
	final_value = 0
	var1.sort()
	var2.sort(reverse=True)
	for i in range(0, len(var1)):
		final_value += min(2 * m, min(var1[i], var2[i]))
	print(final_value)


t = int(input())
for _ in range(0, t):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	flag = False
	mini = 9999999999
	el = set()
	movefromA = []
	movefromB = []
	lengtha = lengthb = 0
	number1 = {}
	number2 = {}
	for i in arr1:
		if i in number1:
			number1[i] += 1
		else:
			number1[i] = 1
			number2[i] = 0
			el.add(i)
	for i in arr2:
		if i in number2:
			number2[i] += 1
		else:
			number2[i] = 1
			if i not in el:
				number1[i] = 0
				el.add(i)
	for i in el:
		a = number1[i]
		b = number2[i]
		total = a + b
		if total % 2 != 0:
			flag = True
			break
		if mini > i:
			mini = i
		if a < b:
			for j in range(b - a >> 1):
				movefromB.append(i)
				lengthb += 1
		elif b < a:
			for j in range(a - b >> 1):
				movefromA.append(i)
				lengtha += 1
	if lengtha != lengthb:
		flag = True
	if flag:
		print(-1)
		continue
	movefromA.sort()
	movefromB.sort()
	mini *= 2
	lessMinA = 0
	lessMinB = 0
	for i in movefromA:
		if i > mini:
			break
		lessMinA += 1
	greatMinA = lengtha - lessMinA
	for i in movefromB:
		if i > mini:
			break
		lessMinB += 1
	greatMinB = lengthb - lessMinB
	pay = 0
	if lessMinA <= greatMinB:
		for i in movefromA[:lessMinA]:
			pay += i
		for i in movefromB[:lessMinB]:
			pay += i
		pay += mini * (greatMinA - lessMinB)
	else:
		for i in movefromA[:greatMinB]:
			pay += i
		for i in movefromB[:greatMinA]:
			pay += i
		i = greatMinB
		j = greatMinA
		for k in range(lessMinB - greatMinA):
			if movefromA[i] < movefromB[j]:
				pay += movefromA[i]
				i += 1
			else:
				pay += movefromB[j]
				j += 1
	print(pay)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	f1 = dict()
	f2 = dict()
	mn = min(min(a), min(b))
	for d in a:
		if d in f1:
			l = f1[d]
			f1[d] = l + 1
		else:
			f1[d] = 1
	for d in b:
		if d in f2:
			l = f2[d]
			f2[d] = l + 1
		else:
			f2[d] = 1
	tot = dict(f1)
	for d in f2:
		if d in tot:
			l = tot[d]
			tot[d] = l + f2[d]
		else:
			tot[d] = f2[d]
	flg = False
	for d in tot.values():
		if d % 2 != 0:
			flg = True
			break
	if flg:
		print('-1')
		continue
	x = []
	for d in tot:
		t = tot.get(d, 0) // 2
		l = f1.get(d, 0)
		r = f2.get(d, 0)
		if l > t:
			k = l - t
			for i in range(k):
				x.append(d)
		if r > t:
			k = r - t
			for i in range(k):
				x.append(d)
	for i in range(len(x)):
		if x[i] > 2 * mn:
			x[i] = 2 * mn
	x.sort()
	ln = len(x) // 2
	y = x[:ln]
	ans = sum(y)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	minimum = min(min(a), min(b))
	s = set()
	ad = {}
	bd = {}
	for i in a:
		if i in s:
			s.remove(i)
		else:
			s.add(i)
		ad[i] = ad.setdefault(i, 0) + 1
		bd[i] = bd.setdefault(i, 0) - 1
	for i in b:
		if i in s:
			s.remove(i)
		else:
			s.add(i)
		bd[i] = bd.setdefault(i, 0) + 1
		ad[i] = ad.setdefault(i, 0) - 1
	if len(s) > 0:
		print('-1')
		continue
	a = []
	b = []
	for i in ad.keys():
		if ad[i] > 0:
			a.extend([i] * (ad[i] // 2))
	for i in bd.keys():
		if bd[i] > 0:
			b.extend([i] * (bd[i] // 2))
	cost = 0
	a.sort()
	b.sort()
	for i in range(len(a)):
		cost += min(min(a[i], b[len(a) - 1 - i]), 2 * minimum)
	print(cost)


for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	A = {}
	B = {}
	x = 0
	Min = 10 ** 9
	for i in a:
		if i in list(A.keys()):
			A[i] += 1
		else:
			A[i] = 1
		if i < Min:
			Min = i
		x = x ^ i
	for i in b:
		if i in list(B.keys()):
			B[i] += 1
		else:
			B[i] = 1
		if i < Min:
			Min = i
		x = x ^ i
	if x != 0:
		print('-1')
		continue
	a = []
	b = []
	for i in list(A.keys()):
		if i in list(B.keys()) and A[i] == B[i]:
			pass
		elif i in list(B.keys()):
			if A[i] > B[i]:
				for j in range((A[i] - B[i]) // 2):
					a.append(i)
		else:
			for j in range(A[i] // 2):
				a.append(i)
	for i in list(B.keys()):
		if i in list(A.keys()) and A[i] == B[i]:
			pass
		elif i in list(A.keys()):
			if B[i] > A[i]:
				for j in range((B[i] - A[i]) // 2):
					b.append(i)
		else:
			for j in range(B[i] // 2):
				b.append(i)
	a = sorted(a)
	b = sorted(b)
	j = -1
	if len(a) != len(b):
		print('-1')
		continue
	cost = 0
	for i in range(len(a)):
		if min(a[i], b[j]) < 2 * Min:
			cost += min(a[i], b[j])
		else:
			cost += 2 * Min
		j -= 1
	print(cost)


t = int(input())
for _ in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	mp = {}
	for i in l1:
		if i in mp:
			mp[i] += 1
		else:
			mp[i] = 1
	for i in l2:
		if i in mp:
			mp[i] -= 1
		else:
			mp[i] = -1
	mini = 2 << 30
	error = False
	l1 = []
	l2 = []
	for (k, v) in list(mp.items()):
		mini = min(mini, k)
		if abs(v) % 2 == 1:
			error = True
		if v > 0:
			v = v // 2
			for _ in range(v):
				l1.append(k)
		if v < 0:
			v = abs(v) // 2
			for _ in range(v):
				l2.append(k)
	if error == True or len(l1) != len(l2):
		print(-1)
		continue
	ans = 0
	for i in range(len(l1)):
		ans += min([2 * mini, l1[i], l2[i]])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	listt1 = [int(e) for e in input().split()]
	listt2 = [int(e) for e in input().split()]
	m = min(min(listt1), min(listt2))
	dic = {}
	(flag, flag2) = (True, True)
	for e in listt1:
		if e not in dic:
			dic[e] = 1
		else:
			dic[e] += 1
	for e in listt2:
		if e not in dic:
			dic[e] = 1
		else:
			dic[e] += 1
	for e in dic:
		if dic[e] % 2 == 1:
			flag = False
	dic2 = {}
	listt1.sort()
	listt2.sort()
	for e in dic:
		if dic[e] % 2:
			flag2 = False
			break
		else:
			dic2[e] = dic[e] // 2
	if flag2 == 0:
		print(-1)
		continue
	ref = dic2.copy()
	listt11 = []
	listt22 = []
	for i in range(0, n):
		if ref[listt1[i]]:
			ref[listt1[i]] -= 1
		else:
			listt11.append(listt1[i])
	ref = dic2.copy()
	for i in range(0, n):
		if ref[listt2[i]]:
			ref[listt2[i]] -= 1
		else:
			listt22.append(listt2[i])
	if len(listt11) == 0:
		print(0)
		continue
	if len(listt11) != len(listt22):
		print(-1)
		continue
	final_value = 0
	listt11.sort()
	listt22.sort(reverse=True)
	for i in range(0, len(listt11)):
		final_value += min(2 * m, min(listt11[i], listt22[i]))
	print(final_value)


for _ in range(int(input())):
	N = int(input())
	A = [int(v) for v in input().split()]
	B = [int(v) for v in input().split()]
	minAB = min(min(A), min(B))
	h = {}
	for ele in A:
		if ele in h:
			h[ele][0] += 1
		else:
			h[ele] = [1, 0]
	for ele in B:
		if ele in h:
			h[ele][1] += 1
		else:
			h[ele] = [0, 1]
	flag = 0
	res = 0
	(AtoB, BtoA, swaps) = ([], [], [])
	for (k, v) in h.items():
		if v[0] == v[1]:
			pass
		elif (v[0] + v[1]) % 2 != 0:
			res = -1
			flag = 1
			break
		else:
			b = abs(v[0] - v[1]) // 2
			if v[0] > v[1]:
				v[1] += b
				v[0] -= b
			else:
				v[0] += b
				v[1] -= b
			for c in range(b):
				swaps.append(k)
	if flag != 1:
		swaps.sort()
		swaps = swaps[:len(swaps) // 2]
		for ele in swaps:
			if ele <= 2 * minAB:
				res += ele
			else:
				res += 2 * minAB
	print(res)