There are two groups, one of $N$ boys and the other of $N$ girls numbered from $1$ to $N$.

You are given two arrays $A$ and $B$ containing $N$ numbers each, denoting the height of boys and girls in the group.
You have to form $N$ couples, where each couple will consist of $1$ boy and $1$ girl. 

Each couple has a LIKENESS VALUE, where
LIKENESS VALUE = height of girl in the couple + height of boy in that couple.

You have to form $N$ couples in such a way that the maximum of LIKENESS VALUE of all the couples is minimum.

Note:-  No boy or girl can form more than one couple.

------ 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$:- number of boys and number of girls in the group.
The second line of each test case contains $N$ space-separated integers, denoting the height of $N$ boys.
The third line of each test case contains $N$ space-separated integers, denoting the height of $N$ girls.

------  Output ------

For each test case, print the maximum LIKENESS VALUE in a new line.

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

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 2*10^{4}$
$1 ≤ A_{i}, B_{i} ≤ 10^{9}$ , for all $1 ≤ i  ≤  N $

----- Sample Input 1 ------ 
1
3
4 5 1
2 2 2
----- Sample Output 1 ------ 
7
----- explanation 1 ------ 
You can form couples of boy and girl with index pair $(1,1), (2,2), (3,3)$. So, the Likeness value of the three couples will be $(4+2), (5+2), (1+2) = 6,7,3$. The maximum value will be $7$ and there are no other ways that can minimize the maximum value$(7)$.

Source: codechef | Difficulty: MEDIUM
Tags: Sorting

Greedy algorithms


Solutions:
for _ in range(int(input())):
	N = int(input())
	boys = sorted(list(map(int, input().split())))
	girls = sorted(list(map(int, input().split())), reverse=True)
	maxx = -1
	for i in zip(boys, girls):
		maxx = max(maxx, sum(i))
	print(maxx)


x = int(input())
ander = []
for tte in range(0, x):
	e = int(input())
	lp = str(input())
	rr = lp.split(' ')
	mut = str(input())
	eewq = mut.split(' ')
	ssa = []
	for bbc in rr:
		ssa.append(int(bbc))
	gge = []
	for iiew in eewq:
		gge.append(int(iiew))
	aswq = [ssa, gge]
	ander.append(aswq)
for cxz in ander:
	gte = cxz[0]
	eewa = cxz[1]
	gte.sort()
	eewa.sort()
	eewa.reverse()
	ab = 0
	for inre in range(0, len(gte)):
		iirew = gte[inre] + eewa[inre]
		if iirew > ab:
			ab = iirew
	print(ab)


t = int(input())
for _ in range(t):
	n = int(input())
	boys = list(map(int, input().split()))
	girls = list(map(int, input().split()))
	maximum = 0
	boys.sort()
	girls.sort(reverse=True)
	for i in range(n):
		likeness = boys[i] + girls[i]
		maximum = max(maximum, likeness)
	print(maximum)


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	list2 = list(map(int, input().split()))
	list1.sort(reverse=True)
	list2.sort()
	list3 = []
	for x in range(n):
		list3.append(list1[x] + list2[x])
	print(max(list3))


for i in range(int(input())):
	n = int(input())
	height_boys = list(map(int, input().split(' ')))
	height_girls = list(map(int, input().split(' ')))
	height_boys.sort(reverse=True)
	height_girls.sort()
	values = []
	for j in range(n):
		values.append(height_girls[j] + height_boys[j])
	print(max(values))


for _ in range(int(input())):
	n = int(input())
	boy = sorted(list(map(int, input().split())))
	girl = sorted(list(map(int, input().split())))
	likeness = [boy[i] + girl[-(i + 1)] for i in range(n)]
	print(max(likeness))


for _ in range(int(input())):
	n = int(input())
	boy_heights = sorted(list(map(int, input().split())))
	girl_heights = sorted(list(map(int, input().split())), reverse=True)
	m = -1
	for i in range(n):
		if boy_heights[i] + girl_heights[i] > m:
			m = boy_heights[i] + girl_heights[i]
	print(m)


class likeness:

	def __init__(self):
		self.n = int(input())
		self.l1 = list(map(int, input().split()))
		self.l2 = list(map(int, input().split()))

	def find(self):
		self.l1.sort()
		self.l2.sort(reverse=True)
		self.max = self.l1[0] + self.l2[0]
		for i in range(1, self.n):
			self.max = max(self.max, self.l1[i] + self.l2[i])
		print(self.max)
for i in range(int(input())):
	obj = likeness()
	obj.find()


for case in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = list(map(int, input().split()))
	b.sort(reverse=True)
	s = 0
	for i in range(n):
		s = max(s, a[i] + b[i])
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	l = []
	for j in range(n):
		l.append(a[j] + b[-(j + 1)])
	print(max(l))


for _ in range(int(input())):
	n = int(input())
	boys_height = sorted(list(map(int, input().split())))
	girls_height = sorted(list(map(int, input().split())), reverse=True)
	mx = -1
	for i in range(n):
		if boys_height[i] + girls_height[i] > mx:
			mx = boys_height[i] + girls_height[i]
	print(mx)


for i in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	m = list(map(int, input().split()))
	m.sort(reverse=True)
	for j in range(n):
		m[j] = m[j] + l[j]
	print(max(m))


from collections import deque
for _ in range(int(input())):
	n = int(input())
	(a, b) = ([int(x) for x in input().split()], [int(x) for x in input().split()])
	a.sort()
	b.sort()
	a = deque(a)
	b = deque(b)
	m = 0
	for i in range(n):
		(x, y) = (a.popleft(), b.pop())
		if x + y > m:
			m = x + y
	print(m)


n = int(input())
for i in range(n):
	num = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr1.sort()
	arr2.sort()
	arr2 = arr2[::-1]
	list1 = []
	for i in range(num):
		list1.append(arr1[i] + arr2[i])
	print(max(list1))


def solve():
	n = int(input())
	boys = list(map(int, input().split()))
	girls = list(map(int, input().split()))
	boys.sort()
	girls.sort(reverse=True)
	maxi = -float('inf')
	for i in range(n):
		maxi = max(maxi, boys[i] + girls[i])
	print(maxi)
t = int(input())
for _ in range(t):
	solve()


from sys import stdin
input = stdin.readline
for i in range(int(input())):
	input()
	c = 2
	for (i, j) in zip(sorted(map(int, input().split())), sorted(map(int, input().split()), reverse=True)):
		c = i + j if i + j > c else c
	print(c)


for i in range(int(input())):
	input()
	c = 2
	for (i, j) in zip(sorted(map(int, input().split())), sorted(map(int, input().split()), reverse=True)):
		if i + j > c:
			c = i + j
	print(c)


for i in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	g = list(map(int, input().split()))
	b.sort(reverse=True)
	g = sorted(g, reverse=False)
	x = [int(b[i]) + int(g[i]) for i in range(n)]
	print(max(x))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	b = b[::-1]
	v = []
	for i in range(n):
		v.append(a[i] + b[i])
	print(max(v))


for tc in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	g = list(map(int, input().split()))
	b.sort()
	g.sort(reverse=True)
	maxval = 0
	for i in range(n):
		maxval = max(maxval, b[i] + g[i])
	print(maxval)


t = int(input())
for i in range(t):
	n = int(input())
	boys = list(map(int, input().split()))
	girls = list(map(int, input().split()))
	boys.sort()
	girls.sort()
	likeness = []
	temp = n - 1
	for i in range(n):
		value = boys[i] + girls[temp]
		likeness.append(value)
		temp -= 1
	print(max(likeness))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort(reverse=True)
	s = []
	for i in range(n):
		s.append(a[i] + b[i])
	print(max(s))


for t in range(int(input())):
	student = int(input())
	boys = list(map(int, input().split()))
	girl = list(map(int, input().split()))
	boys.sort()
	girl.sort()
	couple = []
	for i in range(student):
		h = boys[i] + girl[student - i - 1]
		couple = [h] + couple
	couple.sort()
	print(couple[-1])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort(reverse=True)
	ma = -999
	for i in range(n):
		if a[i] + b[i] > ma:
			ma = a[i] + b[i]
	print(ma)


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr1.sort()
	arr2.sort()
	arr2.reverse()
	arr = [arr1[i] + arr2[i] for i in range(n)]
	print(max(arr))


for i in range(int(input())):
	n = int(input())
	boys = list(map(int, input().split()))
	girls = list(map(int, input().split()))
	boys.sort()
	girls.sort()
	girls.reverse()
	ans = []
	for num in range(n):
		ans.append(boys[num] + girls[num])
	print(max(ans))


t = int(input())
while t:
	n = int(input())
	boys = list(map(int, input().split(' ')))
	girls = list(map(int, input().split(' ')))
	boys.sort()
	girls.sort(reverse=True)
	maxnum = []
	for i in range(n):
		maxnum.append(boys[i] + girls[i])
	print(max(maxnum))
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	first = list(map(int, input().split()))
	second = list(map(int, input().split()))
	first.sort()
	second.sort()
	second = second[::-1]
	list1 = []
	for i in range(n):
		list1.append(first[i] + second[i])
	print(max(list1))


for _ in range(int(input())):
	couples = int(input())
	first = list(map(int, input().split()))
	second = list(map(int, input().split()))
	first.sort()
	second.sort()
	second = second[::-1]
	scores = []
	for num in range(couples):
		scores.append(first[num] + second[num])
	print(max(scores))


def solve():
	for _ in range(int(input())):
		_ = int(input())
		A = sorted(map(int, input().split()))
		B = sorted(map(int, input().split()), reverse=True)
		max_likeness = 0
		for (a, b) in zip(A, B):
			max_likeness = max(max_likeness, a + b)
		print(max_likeness)
solve()


testCases = int(input())
for case in range(testCases):
	n = int(input())
	boys = []
	girls = []
	for i in input().split(' '):
		boys.append(int(i))
	for i in input().split(' '):
		girls.append(int(i))
	boys.sort()
	girls.sort()
	likeness = []
	for i in range(n):
		likeness.append(boys[i] + girls[n - i - 1])
	print(max(likeness))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort()
	max = 0
	for j in range(n):
		if a[j] + b[j] > max:
			max = a[j] + b[j]
	print(max)


for _ in range(int(input())):
	n = int(input())
	boys = list(map(int, input().split()))
	girls = list(map(int, input().split()))
	lst = []
	boys.sort()
	girls.sort()
	r = girls[::-1]
	for i in range(n):
		lst.append(boys[i] + r[i])
	print(max(lst))


for i in range(int(input())):
	n = int(input())
	hb = list(map(int, input().split()))
	hg = list(map(int, input().split()))
	hb = sorted(hb, reverse=True)
	hg = sorted(hg)
	likness = []
	for i in range(n):
		lik = hb[i] + hg[i]
		likness.append(lik)
	print(max(likness))


for i in range(int(input())):
	int(input())
	m = sorted(list(map(int, input().split())))
	n = sorted(list(map(int, input().split())), reverse=True)
	print(max([sum([i, j]) for (i, j) in zip(m, n)]))


for z in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	g = list(map(int, input().split()))
	b.sort()
	g.sort()
	l = []
	for i in range(n):
		l.append(b[i] + g[n - i - 1])
	print(max(l))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort(reverse=True)
	b = [int(x) for x in input().split()]
	b.sort()
	h = 0
	for i in range(n):
		if a[i] + b[i] > h:
			h = a[i] + b[i]
	print(h)


T = int(input())
for i in range(T):
	N = int(input())
	B = list(map(int, input().split()))
	G = list(map(int, input().split()))
	B.sort()
	G.sort()
	G = G[::-1]
	couples = []
	for num in range(N):
		couples.append(B[num] + G[num])
	print(max(couples))


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	g = list(map(int, input().split()))
	b.sort()
	g.sort()
	g = g[::-1]
	a = [0] * n
	for i in range(n):
		a[i] = b[i] + g[i]
	print(max(a))


from itertools import product as p
for _ in range(int(input())):
	n = int(input())
	b = sorted(list(map(int, input().split(' '))))
	g = list(map(int, input().split(' ')))
	g.sort(reverse=True)
	print(max([b[x] + g[x] for x in range(n)]))


for _ in range(int(input())):
	n = int(input())
	boys_height = sorted(list(map(int, input().split())))
	girls_height = list(map(int, input().split()))
	girls_height.sort(reverse=True)
	likeness_value = []
	for i in range(n):
		likeness_value.append(boys_height[i] + girls_height[i])
	print(max(likeness_value))


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	g = list(map(int, input().split()))
	b.sort()
	g.sort()
	g = g[::-1]
	scores = []
	for i in range(n):
		scores.append(b[i] + g[i])
	print(max(scores))


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	g = list(map(int, input().split()))
	b.sort()
	g.sort(reverse=True)
	maxx = -1
	for i in range(n):
		maxx = max(maxx, b[i] + g[i])
	print(maxx)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	g = list(map(int, input().split()))
	b.sort(reverse=True)
	g.sort()
	maxx = 0
	for i in range(n):
		if g[i] + b[i] > maxx:
			maxx = g[i] + b[i]
	print(maxx)


t = int(input())
while t:
	s = []
	n = int(input())
	B = [int(i) for i in input().split()]
	G = [int(i) for i in input().split()]
	B.sort()
	G = sorted(G, reverse=True)
	for i in range(n):
		s.append(B[i] + G[i])
	print(max(s))
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b.sort()
	a.sort(reverse=True)
	l = []
	for i in range(0, n):
		c = b[i] + a[i]
		l.append(c)
		c = 0
	print(max(l))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = list(map(int, input().split()))
	l.sort()
	l1.sort()
	s = []
	for i in range(n):
		s.append(l[i] + l1[n - 1 - i])
	print(max(s))


z = int(input())
while z:
	n = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	A.sort()
	B.sort()
	C = []
	for j in range(n):
		C.append(A[j] + B[n - j - 1])
	print(max(C))
	z -= 1


t = int(input())
for i in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	A.sort()
	B.sort()
	C = []
	for j in range(n):
		C.append(A[j] + B[n - j - 1])
	print(max(C))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	b = b[::-1]
	s = [0 for x in range(n)]
	for x in range(n):
		s[x] = a[x] + b[x]
	print(max(s))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort(reverse=True)
	ma = 0
	for i in range(n):
		if a[i] + b[i] > ma:
			ma = a[i] + b[i]
	print(ma)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a1 = list(map(int, input().split()))
	a2 = list(map(int, input().split()))
	a1.sort(reverse=False)
	a2.sort(reverse=True)
	maximum = -1
	for i in range(n):
		maximum = max(maximum, a1[i] + a2[i])
	print(maximum)


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = sorted(list(map(int, input().split())))
	list2 = sorted(list(map(int, input().split())), reverse=True)
	a = [list1[i] + list2[i] for i in range(n)]
	print(max(a))


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	b.sort()
	c.sort(reverse=True)
	d = []
	for i in range(a):
		d.append(b[i] + c[i])
	print(max(d))


for i in range(int(input())):
	d = int(input())
	e = list(map(int, input().split()))
	f = list(map(int, input().split()))
	e.sort()
	f.sort()
	f.reverse()
	g = []
	for k in range(d):
		g.append(e[k] + f[k])
	print(max(g))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	b.reverse()
	m = 0
	for i in range(n):
		if a[i] + b[i] > m:
			m = a[i] + b[i]
	print(m)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l1.sort()
	l2.sort()
	l2.reverse()
	m = 0
	for i in range(n):
		if l1[i] + l2[i] > m:
			m = l1[i] + l2[i]
	print(m)


t = int(input())
for i in range(t):
	n = int(input())
	bh = list(map(int, input().split()))
	gh = list(map(int, input().split()))
	s = []
	bh.sort()
	gh.sort(reverse=True)
	for i in range(len(bh)):
		s.append(bh[i] + gh[i])
	print(max(s))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort(reverse=True)
	ans = max([a[i] + b[i] for i in range(n)])
	print(ans)


n = int(input())
for i in range(n):
	l = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	a.sort()
	b.sort()
	c = []
	for x in range(l):
		c.append(a[x] + b[l - 1 - x])
	print(max(c))


for _ in range(int(input())):
	N = int(input())
	boys = list(map(int, input().split()))
	girls = list(map(int, input().split()))
	boys.sort()
	girls.sort(reverse=True)
	mx = -1
	for i in range(N):
		mx = max(mx, boys[i] + girls[i])
	print(mx)


T = int(input())
for I in range(T):
	n = int(input())
	max = 0
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	a.sort()
	b.sort(reverse=True)
	for i in range(0, n):
		if max < a[i] + b[i]:
			max = a[i] + b[i]
	print(max)


for _ in range(int(input())):
	n = int(input())
	b = sorted(list(map(int, input().split())))
	g = sorted(list(map(int, input().split())))[::-1]
	m = 0
	for i in range(n):
		if b[i] + g[i] > m:
			m = b[i] + g[i]
	print(m)


def couples(g, b, length):
	g.sort()
	b.sort(reverse=True)
	k = max([g[i] + b[i] for i in range(length)])
	return k
for i in range(int(input())):
	length = int(input())
	b = [int(i) for i in input().split()]
	g = [int(i) for i in input().split()]
	print(couples(g, b, length))


for _ in range(int(input())):
	i = int(input())
	j = sorted(list(map(int, input().split())))
	k = list(reversed(sorted(list(map(int, input().split())))))
	maxi = 0
	for val in range(i):
		maxi = max(maxi, j[val] + k[val])
	print(maxi)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	g = list(map(int, input().split()))
	b.sort(reverse=True)
	g.sort()
	max_lik = 0
	for i in range(n):
		max_lik = max(max_lik, b[i] + g[i])
	print(max_lik)


reply = []
for _ in range(int(input())):
	n = int(input())
	boys = []
	girls = []
	for i in input().split():
		boys.append(int(i))
	for i in input().split():
		girls.append(int(i))
	boys.sort()
	girls.sort()
	li = []
	for i in range(n):
		li.append(boys[i] + girls[n - i - 1])
	reply.append(max(li))
for i in reply:
	print(i)