N boys and N girls attend a dance class, where N is odd. For today's practice session, they need to form N boy-girl pairs.

The i-th boy has a happiness value of A_{i} and the i-th girl has a happiness value of B_{i}.
A pair consisting of the i-th boy and the j-th girl has a happiness value of A_{i} + B_{j}.

Let the happiness values of the N pairs be C_{1}, C_{2}, \ldots, C_{N}. The dance instructor would like it if many of the pairs have a high happiness value, and passes the task to you — find the maximum possible value of the median of C, if the boy-girl pairs are chosen optimally.

Note: The median of a odd-sized list of integers is the middle number when they are sorted. For example, the median of [1] is 1, the median of [1, 5, 2] is 2, and the median of [30, 5, 5, 56, 3] is 5.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of three lines of input.
- The first line of each test case contains a single integer N.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — the happiness values of the boys.
- The third line of each test case contains N space-separated integers B_{1}, B_{2}, \ldots, B_{N} — the happiness values of the girls.

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

For each test case, output on a new line the maximum possible median happiness of the N pairs.

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

$1 ≤ T ≤ 3 \cdot 10^{4}$
$1 ≤ N < 3\cdot 10^{5}$
$N$ is odd
$1 ≤ A_{i}, B_{i} ≤ 10^{9}$ for each valid $i$
- The sum of $N$ across all test cases won't exceed $3 \cdot 10^{5}$.

------ subtasks ------ 

Subtask 1 (10 points):
The sum of $N$ across all test cases won't exceed $10$.
Subtask 2 (30 points):
The sum of $N$ across all test cases won't exceed $4000$.
Subtask 3 (60 points):
No further constraints.

----- Sample Input 1 ------ 
3
1
10
25
3
1 6 6
2 2 7
5
10 4 93 5 16
4 34 62 6 26

----- Sample Output 1 ------ 
35
8
50

----- explanation 1 ------ 
Test case $1$: There is only one boy and one girl, so they must be paired with each other. The happiness value of the pair is $10 + 25 = 35$, and it is also the median.

Test case $2$: Pair $A_{1}$ with $B_{3}$, $A_{2}$ with $B_{2}$, and $A_{3}$ with $B_{3}$. The happiness values are then $[1+7, 2+6, 2+6] = [8, 8, 8]$, with a median of $8$. It can be shown that this is the maximum possible median.

Test case $3$: One way of achieving a median of $50$ is as follows:
- Pair $A_{1}$ with $B_{3}$, for a happiness of $10 + 62 = 72$
- Pair $A_{2}$ with $B_{4}$, for a happiness of $4 + 6 = 10$
- Pair $A_{3}$ with $B_{5}$, for a happiness of $93 + 26 = 119$
- Pair $A_{4}$ with $B_{1}$, for a happiness of $5 + 4 = 9$
- Pair $A_{5}$ with $B_{2}$, for a happiness of $16 + 34 = 50$

The happiness values are $[72, 10, 119, 9, 50]$, with a median of $50$. It can be shown that no other pairing obtains a strictly larger median.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms


Solutions:
for _ in range(int(input())):
	n = int(input())
	ali = list(map(int, input().split()))
	bli = list(map(int, input().split()))
	ali.sort()
	bli.sort()
	k = n // 2
	ali = ali[k:]
	bli = bli[k:]
	lst = list()
	ln = len(ali)
	for i in range(ln):
		a = ali[i] + bli[ln - i - 1]
		lst.append(a)
	lst.sort()
	print(lst[0])


t = int(input())
for _ in range(t):
	n = int(input())
	boys = list(map(int, input().split()))
	girls = list(map(int, input().split()))
	boys.sort()
	girls.sort()
	b = []
	g = []
	ans = []
	for i in range(n // 2, n):
		b.append(boys[i])
		g.append(girls[i])
	g.reverse()
	for i in range(len(g)):
		ans.append(b[i] + g[i])
	print(min(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	brr = []
	arr = []
	br = []
	a.sort()
	b.sort()
	for i in range(n // 2, n):
		arr.append(a[i])
		brr.append(b[i])
	for i in range(len(arr)):
		arr[i] += brr[len(brr) - 1 - i]
	print(min(arr))


for i in range(int(input())):
	n = int(input())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))
	C = []
	for i in range(n // 2, n):
		j = n - (i - n // 2) - 1
		C.append(A[i] + B[j])
	C = sorted(C)
	print(C[0])


import sys
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	A.sort()
	B.sort()
	a = (N - 1) // 2
	b = N - 1
	med = sys.maxsize
	for i in range(a, N):
		med = min(med, A[i] + B[b])
		b -= 1
	print(med)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	A.sort()
	B.sort()
	a = (N - 1) // 2
	b = N - 1
	med = 1e+18
	for i in range(a, N):
		med = min(med, A[i] + B[b])
		b -= 1
	print(med)


import math

def test():
	N = int(input())
	As = list(map(int, input().split()))
	Bs = list(map(int, input().split()))
	As.sort()
	Bs.sort()
	C = []
	for i in range(0, math.ceil(N / 2)):
		C.append(As[N - i - 1] + Bs[i + N // 2])
	print(min(C))
tests = int(input())
for i in range(tests):
	test()


t = int(input())
for _ in range(t):
	n = int(input())
	b = sorted(list(map(int, input().split())))
	g = sorted(list(map(int, input().split())))
	i = n // 2
	b = b[i:]
	g = g[i:]
	g.reverse()
	med = [k + j for (k, j) in zip(b, g)]
	print(min(med))


def solution():
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	A.sort()
	B.sort()
	start = (N - 1) // 2
	end = N - 1
	median = 1e+18
	for i in range(start, N):
		median = min(median, A[i] + B[end])
		end -= 1
	print(median)
t = int(input())
while t > 0:
	t = t - 1
	solution()


for testcase in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if n == 1:
		print(a[0] + b[0])
		continue
	a.sort()
	b.sort()
	arra = []
	arrb = []
	for i in range(n):
		if i < n // 2:
			arra.append(a[i] + b[i])
			arrb.append(a[i] + b[i])
		else:
			arra.append(a[i] + b[n - 1 - i + n // 2])
			arrb.append(b[i] + a[n - 1 - i + n // 2])
	arra.sort()
	arrb.sort()
	print(max(arra[n // 2], arrb[n // 2]))


def solve():
	N = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	if N == 1:
		print(A[0] + B[0])
		return
	M = (N + 1) // 2
	A.sort()
	B.sort()
	ans = 10 ** 10
	i = M - 1
	j = N - 1
	while i < N:
		ans = min(ans, A[i] + B[j])
		i += 1
		j -= 1
	print(ans)

def main():
	T = int(input())
	while T > 0:
		solve()
		T = T - 1
main()


t = int(input())
for _ 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()
	a = a[n // 2:]
	b = b[n // 2:]
	ans = 10 ** 18
	for i in range(len(a)):
		ans = min(ans, b[i] + a[len(a) - 1 - i])
	print(ans)


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=1)
	z = []
	for k in range(n // 2 + 1, n // 2 + 2):
		y = []
		for i in range(n):
			y.append(A[i] + B[(i + k) % n])
		y.sort()
		print(y[n // 2])


for T in range(int(input())):
	N = int(input())
	A = sorted(map(int, input().split()), reverse=True)[:N // 2 + 1]
	B = sorted(map(int, input().split()), reverse=True)[:N // 2 + 1]
	print(min((A[i] + B[N // 2 - i] for i in range(N // 2 + 1))))


t = int(input())
while t:
	n = int(input())
	med = n // 2
	a = sorted(map(int, input().split()))
	b = sorted(map(int, input().split()))
	new_b = b[0:med] + sorted(b[med:], reverse=True)
	c = []
	for i in range(n):
		c.append(a[i] + new_b[i])
	c = sorted(c)
	print(c[med])
	t -= 1


for test in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	A.sort()
	B.sort()
	m = 1999999999
	mid = N // 2
	for i in range(mid, N):
		j = N - 1 - (i - mid)
		m = min(m, A[i] + B[j])
	print(m)


cnt = int(input())
for i in range(cnt):
	N = int(input())
	Ais = list(map(int, input().split()))
	Bis = list(map(int, input().split()))
	Ais.sort()
	Bis.sort()
	Ais = Ais[int((N - 1) / 2):]
	Bis = Bis[int((N - 1) / 2):]
	Bis.sort(reverse=True)
	median = 2000000001
	for j in range(len(Ais)):
		if median > Ais[j] + Bis[j]:
			median = Ais[j] + Bis[j]
	print(median)


import heapq
from math import gcd, sqrt, ceil

def ti():
	return tuple(map(int, input().split()))

def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	a = li()
	b = li()
	a.sort()
	b.sort()
	for i in range(n // 2):
		a[i] += b[i]
	for i in range(n // 2, n):
		a[i] += b[n + (n // 2 - i) - 1]
	a.sort()
	print(a[n // 2])


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(reverse=True)
	half = b[n // 2 + 1:]
	half1 = half[::-1]
	b1 = half1 + b[0:n // 2 + 1]
	l = []
	for i in range(0, len(a)):
		s = a[i] + b1[i]
		l.append(s)
	l.sort()
	print(l[len(l) // 2])


for _ in range(int(input())):
	numberOfBoys = int(input())
	listOfBoys = list(map(int, input().split()))
	listOfGirls = list(map(int, input().split()))
	listOfBoys.sort()
	listOfGirls.sort()
	listOfHappiness = []
	medianPos = int(numberOfBoys / 2)
	for i in range(0, medianPos):
		listOfHappiness.append(listOfGirls[i] + listOfBoys[i])
	start = medianPos
	end = numberOfBoys - 1
	while True:
		listOfHappiness.append(listOfGirls[start] + listOfBoys[end])
		start += 1
		end -= 1
		if start >= numberOfBoys:
			break
	listOfHappiness.sort()
	print(listOfHappiness[medianPos])


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


import sys
t = int(input())
for _ 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()
	e = n - 1
	ans = sys.maxsize
	for i in range(n // 2, n, 1):
		ans = min(ans, a[i] + b[e])
		e -= 1
	print(ans)


for iii in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if n % 2 == 0:
		n2 = int(n / 2) - 1
	else:
		n2 = int(n / 2)
	a.sort()
	b.sort()
	a = a[:n2] + sorted(a[n2:], reverse=True)
	for i in range(n):
		a[i] += b[i]
	a.sort()
	print(a[n2])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(sorted(map(int, input().split())))
	b = list(sorted(map(int, input().split())))
	c = []
	s = 0
	for j in range(n // 2):
		c.append(a[s] + b[j])
		s += 1
	for k in range(n - 1, n // 2 - 1, -1):
		c.append(a[s] + b[k])
		s += 1
	c.sort()
	print(c[n // 2])


for _ in range(int(input())):
	n = int(input())
	a = list(sorted(map(int, input().split())))
	b = list(sorted(map(int, input().split())))
	c = []
	ai = 0
	for i in range(n // 2):
		c.append(a[ai] + b[i])
		ai += 1
	for j in range(n - 1, n // 2 - 1, -1):
		c.append(a[ai] + b[j])
		ai += 1
	c.sort()
	print(c[n // 2])


for _ in range(int(input())):
	n = int(input())
	boiz = list(map(int, input().split()))
	grils = list(map(int, input().split()))
	boiz.sort()
	grils.sort()
	boiz = boiz[len(boiz) // 2:]
	grils = grils[len(grils) // 2:]
	ans = []
	for i in range(len(boiz)):
		ans.append(boiz[i] + grils[len(grils) - 1 - i])
	print(min(ans))


def mxmed(n, a, b):
	a.sort()
	b.sort()
	s = (n - 1) // 2
	e = n - 1
	med = 1e+18
	for i in range(s, n):
		med = min(med, a[i] + b[e])
		e = e - 1
	print(med)
	return
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mxmed(n, a, b)


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(reverse=True)
	L = []
	for i in range(N // 2, N):
		L.append(A[i] + B[i - N // 2])
	print(min(L))


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = list(map(int, input().strip().split()))
	list2 = list(map(int, input().strip().split()))
	list1.sort()
	list2.sort()
	mid = n // 2
	list1 = list1[mid:]
	list2 = list2[mid:]
	list1.sort(reverse=True)
	list3 = [list1[i] + list2[i] for i in range(len(list1))]
	list3.sort()
	print(list3[0])


for _ in range(int(input().strip())):
	n = int(input().strip())
	arr1 = sorted(list((int(i) for i in input().strip().split())))
	arr2 = sorted(list((int(i) for i in input().strip().split())))
	temp = arr2[:n // 2]
	arr2 = temp + arr2[n // 2:][::-1]
	new_arr = []
	for i in range(n):
		new_arr.append(arr1[i] + arr2[i])
	new_arr.sort()
	print(new_arr[n // 2])


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l1.sort()
	l2.sort()
	l11 = l2[0:n // 2]
	l2 = l2[n // 2:]
	l2.reverse()
	l3 = []
	l2 = l11 + l2
	i = 0
	while i < n:
		l3.append(l1[i] + l2[i])
		i += 1
	l3.sort()
	print(l3[n // 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()
	m = (n - 1) // 2
	ans = a[m] + b[n - 1]
	k = n - 1
	for i in range(m, n):
		ans = min(ans, a[i] + b[k])
		k -= 1
	print(ans)


import sys
input = sys.stdin.readline
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()
	start = (n - 1) // 2
	end = n - 1
	median = 1e+18
	for i in range(start, n):
		median = min(median, a[i] + b[end])
		end -= 1
	print(median)
	t -= 1


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	start = n // 2
	end = n - 1
	maxmed = float('inf')
	for i in range(start, n):
		maxmed = min(maxmed, a[i] + b[end])
		end -= 1
	print(maxmed)
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = sorted(a)
	b = sorted(b)
	b = b[::-1]
	temp = []
	for i in range(n // 2, n):
		temp.append(a[i])
	for i in range(0, n // 2):
		temp.append(a[i])
	for i in range(n):
		b[i] = b[i] + temp[i]
	b.sort()
	print(b[n // 2])


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	if n == 1:
		print(arr[0] + brr[0])
	else:
		arr.sort()
		brr.sort()
		arr = arr[n // 2:]
		brr = brr[n // 2:][::-1]
		ans = float('inf')
		for (a, b) in zip(arr, brr):
			ans = min(ans, a + b)
		print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	A = sorted(A)[int(N / 2):]
	B = sorted(B)[int(N / 2):]
	B = sorted(B, reverse=True)
	C = [x + y for (x, y) in zip(A, B)]
	sorted(C)
	print(min(C))


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l1.sort()
	l2.sort()
	k = n // 2 + 1
	median = l1[n - 1] + l2[n - 1]
	for i in range(k):
		m = l1[k + i - 1] + l2[n - 1 - i]
		if m < median:
			median = m
	print(median)


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()
	median = a[n - 1] + b[n - 1]
	for i in range(n // 2 + 1):
		if a[n // 2 + i] + b[n - i - 1] < median:
			median = a[n // 2 + i] + b[n - i - 1]
	print(median)


def solve(N, A, B):
	if N == 1:
		return A[0] + B[0]
	A.sort()
	B.sort()
	start = N // 2
	end = N - 1
	res = float('inf')
	while start < N:
		res = min(res, A[start] + B[end])
		start += 1
		end -= 1
	return res
for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print(solve(N, A, B))


for i in range(int(input())):
	n = int(input())
	inp1 = list(map(int, input().split()))
	inp1.sort()
	inp2 = list(map(int, input().split()))
	inp2.sort()
	if n == 1:
		print(inp1[0] + inp2[0])
	else:
		r = inp1[n // 2] + inp2[n - 1]
		for i in range(1, n // 2 + 1):
			if inp1[n // 2 + i] + inp2[n - i - 1] < r:
				r = inp1[n // 2 + i] + inp2[n - i - 1]
		print(r)


from bisect import bisect_left
from re import sub
import re
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys
import copy

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
				ans.append(n // i)
			else:
				c += 2
				ans.append(i)
				ans.append(n // i)
		i += 1
	return ans
	return c

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def count(n):
	ans = 0
	while n:
		ans += n % 10
		n //= 10
	return ans

def lcm(a, b):
	return a * b // math.gcd(a, b)

def check(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def solve():
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l1.sort()
	l2.sort(reverse=True)
	ans = []
	for i in range(n // 2, n):
		ans.append(l1[i] + l2[i - n // 2])
	return min(ans)
for _ in range(int(input())):
	print(solve())


n = int(input())
for i in range(n):
	t = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	b = b[:t // 2] + sorted(b[t // 2:], reverse=True)
	l = [a[i] + b[i] for i in range(t)]
	l.sort()
	print(l[t // 2])


import math
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	start = (n - 1) // 2
	end = n - 1
	median = float('inf')
	for i in range(start, n):
		median = min(median, a[i] + b[end])
		end -= 1
	print(median)
	t -= 1


for i in range(int(input())):
	n = int(input())
	boy = list(map(int, input().split()))
	girl = list(map(int, input().split()))
	boy.sort()
	girl.sort(reverse=True)
	mid = (n - 1) // 2
	k = 0
	median = float('inf')
	for i in range(mid, n):
		median = min(boy[i] + girl[k], median)
		k += 1
	print(median)


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()
	a = a[n // 2:]
	b = b[n // 2:]
	c = [a[x] + b[-1 - x] for x in range(len(a))]
	print(min(c))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = sorted(a)
	b = sorted(b)
	start = n // 2
	end = n
	d = 0
	c = []
	for i in range(start, end):
		d = 0
		d = a[i] + b[end - 1]
		c.append(d)
		end -= 1
	print(min(c))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a1 = [int(x) for x in input().split()]
	a2 = [int(x) for x in input().split()]
	a1.sort()
	a2.sort()
	a1 = a1[(n - 1) // 2:]
	a2 = a2[(n - 1) // 2:]
	a1 = a1[::-1]
	a = []
	for i in range(len(a1)):
		sum = a1[i] + a2[i]
		a.append(sum)
	a.sort()
	print(a[0])


t = int(input())
for test in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	g = list(map(int, input().split()))
	b.sort()
	g.sort()
	i = (n - 1) // 2
	j = n - 1
	mn = float('inf')
	while i < n:
		mn = min(mn, b[i] + g[j])
		i += 1
		j -= 1
	print(mn)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	b = [int(i) for i in input().split()]
	b.sort(reverse=True)
	mid = n // 2
	a = a[mid:]
	b = b[:mid + 1]
	l = []
	for i in range(mid + 1):
		l.append(a[i] + b[i])
	l.sort()
	print(l[0])


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()
	a = a[n // 2:]
	b = b[n // 2:]
	b = b[::-1]
	x = 9999999999
	for i in range(n - n // 2):
		x = min(x, a[i] + b[i])
	print(x)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	mid = len(a) // 2
	i = mid
	j = n - 1
	ans = math.inf
	for _ in range(mid + 1):
		ans = min(ans, a[i] + b[j])
		i += 1
		j -= 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	c = n // 2
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if n == 1:
		print(a[0] + b[0])
		continue
	b = sorted(b, reverse=True)
	a = sorted(a)
	s = []
	ans = []
	for i in range(c, n, 1):
		ans.append(a[i] + b[i - c])
	ans.sort()
	print(ans[0])


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))[n // 2:]
	b = sorted(list(map(int, input().split())))[n // 2:]
	b.sort(reverse=True)
	c = sorted([x + y for (x, y) in zip(a, b)])
	print(c[0])


for i in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	m = list(map(int, input().split()))
	k.sort()
	m.sort()
	median = 1e+18
	start = (n - 1) // 2
	end = n - 1
	for i in range(start, n):
		median = min(median, k[i] + m[end])
		end -= 1
	print(median)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().strip().split()))[:N]
	B = list(map(int, input().strip().split()))[:N]
	A.sort()
	B.sort()
	start = (N - 1) / 2
	end = N - 1
	med = 1000000000000000000000000
	for i in range((N - 1) // 2, N):
		res = A[i] + B[end]
		med = min(res, med)
		end -= 1
	print(med)


def T(A, B):
	C = []
	for i in range(len(A)):
		C.append(A[i] + B[i])
	return C
a = int(input())
for i in range(a):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	if N == 1:
		print(A[0] + B[0])
	else:
		A.sort()
		B.sort()
		b = int((N + 1) / 2) - 1
		C = []
		C += T(A[:b], B[:b])
		C += T(A[b:N], B[N - 1:b - 1:-1])
		C.sort()
		c = C[int((N + 1) / 2) - 1]
		print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	start = (n - 1) // 2
	end = n - 1
	median = 1e+18
	for i in range(start, n):
		median = min(median, a[i] + b[end])
		end -= 1
	print(median)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	res = float('inf')
	for i in range((n - 1) // 2, n):
		res = min(res, a[i] + b[n - 1])
		n -= 1
	print(res)


import numpy as np
t = int(input())
for tests in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	c = []
	x = n - 1
	for i in range(len(a) // 2, len(a)):
		c.append(a[i] + b[x])
		x -= 1
	print(min(c))


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l1.sort()
	l2.sort()
	num = []
	st = n - 1
	for i in range(n // 2, n):
		num.append(l1[i] + l2[st])
		st -= 1
	num.sort()
	print(num[0])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	x = int(n / 2)
	c = []
	for i in range(x):
		c.append(a[i] + b[i])
	for i in range(x + 1):
		c.append(a[i + x] + b[n - i - 1])
	c.sort()
	print(c[x])


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	low = 3 * pow(10, 9)
	mid = (n - 1) // 2
	arr1.sort()
	arr2.sort()
	for i in range(mid, n):
		num = arr1[i] + arr2[n - (i - mid) - 1]
		low = min(low, num)
	print(low)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	k = n // 2
	l = []
	for i in range(k, n):
		l.append(a[i] + b[n + k - i - 1])
	l.sort()
	print(l[0])


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ra = n // 2
	a.sort()
	b.sort()
	a = a[ra:]
	b = b[ra:]
	c = []
	m = len(a)
	for i in range(0, m):
		c.append(a[i] + b[m - 1 - i])
	c.sort()
	print(c[0])


for i in range(int(input())):
	n = int(input())
	l1 = sorted(list(map(int, input().split())))
	l2 = sorted(list(map(int, input().split())))
	m = n // 2
	a1 = l1[m:]
	a2 = l2[::-1]
	a = []
	for i in range(len(a1)):
		a.append(a1[i] + a2[i])
	print(min(a))


t = int(input())
for x in range(t):
	p = []
	f = 0
	N = int(input())
	k = input().split()
	o = input().split()
	k = [int(y) for y in k]
	o = [int(y) for y in o]
	k.sort()
	o.sort()
	for y in range(int(N / 2), N):
		p.append(k[y] + o[len(k) - 1 - f])
		f += 1
	print(min(p))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	a = sorted(a)
	b = sorted(b)
	a1 = a[n // 2:]
	b1 = b[n // 2:]
	b1 = sorted(b1, reverse=True)
	temp = []
	for i in range(len(a1)):
		x = a1[i] + b1[i]
		temp.append(x)
	a2 = a[:n // 2]
	b2 = b[:n // 2]
	b2 = sorted(b2, reverse=True)
	for i in range(len(a2)):
		y = a2[i] + b2[i]
		temp.append(y)
	temp = sorted(temp)
	print(temp[n // 2])


for i in range(int(input())):
	num = int(input())
	arr1 = list(map(int, input().split(' ')))
	arr2 = list(map(int, input().split(' ')))
	arr1.sort()
	arr2.sort()
	medium = num // 2
	arr = arr2[medium:]
	lis1 = arr1[medium:]
	lis2 = arr[::-1]
	ans = []
	for i in range(len(lis1)):
		sm = lis1[i] + lis2[i]
		ans.append(sm)
	ans.sort()
	print(ans[0])


import math
no_test = int(input())
sol = []

def fun(n):
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	a.sort()
	b.sort()
	c = []
	a = a[n // 2:]
	b = b[n // 2:]
	for i in range(n // 2 + 1):
		c.append(a.pop() + b.pop(0))
	c.sort()
	return c[0]
for _ in range(0, no_test):
	a = int(input())
	sol.append(fun(a))
for k in sol:
	print(k)


import math
from collections import Counter
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
mx = 10 ** 5
inp = lambda : int(input())

def easy():
	n = inp()
	s = input()
	v = ['a', 'e', 'i', 'o', 'u']
	consecutive = 0
	for x in s:
		if x not in v:
			consecutive += 1
		else:
			consecutive = 0
		if consecutive == 4:
			return 'no'
	return 'yes'

def make_pal():
	n = inp()
	s = input()
	ev_s = od_s = ''
	for i in range(n):
		if i % 2:
			ev_s += s[i]
		else:
			od_s += s[i]
	ct1 = Counter(ev_s)
	ct2 = Counter(od_s)
	if ct1 == ct2:
		return 'yes'
	else:
		return 'no'

def max_matching():
	n = inp()
	a = ints()
	b = ints()
	if n != 1:
		b.sort()
		a.sort(reverse=True)
		med = 10 ** 10
		half = b[n // 2:]
		for i in range(len(half)):
			med = min(med, a[i] + half[i])
		return med
	else:
		return a[0] + b[0]

def largest():
	n = inp()
	arr = ints()
	arr.sort()
	cts = 0
	parents = 0
	while cts != n:
		if parents + arr[cts] <= n - 1:
			parents += arr[cts]
			cts += 1
		else:
			break
	return cts

def cons_xor():
	n = inp()
	a = input()
	b = input()
	if a.count('1') == 0 and b.count('1'):
		print('no')
	else:
		prev_i = None
		temp_a = temp_b = ''
		for i in range(n):
			if a[i] != b[i]:
				temp_a += a[i]
				temp_b += b[i]
			else:
				...
			prev_i = i
for _ in range(inp()):
	print(max_matching())


from operator import add
import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort(reverse=True)
	mid = math.floor(n / 2)
	c = list(map(add, a[mid:n], b[:mid + 1]))
	print(min(c))


for t in range(int(input())):
	n = int(input())
	boys = [int(s) for s in input().split()]
	girls = [int(s) for s in input().split()]
	boys = sorted(boys)
	girls = sorted(girls)
	if n == 1:
		print(boys[0] + girls[0])
		continue
	mid = (n - 1) // 2
	ans = 1e+19
	end = n - 1
	for i in range(mid, n):
		ans = min(ans, boys[i] + girls[end])
		end -= 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	a = a[n // 2:]
	b = b[n // 2:]
	b.reverse()
	c = [a[i] + b[i] for i in range(len(a))]
	c.sort()
	print(c[0])


for _ in range(int(input())):
	l = int(input())
	lis1 = list(map(int, input().split()))
	lis2 = list(map(int, input().split()))
	lis3 = []
	if len(lis1) == 1 and len(lis2) == 1:
		print(lis1[0] + lis2[0])
	else:
		lis1.sort()
		lis2.sort()
		lis1 = lis1[l // 2:]
		lis2 = lis2[l // 2:]
		for i in range(len(lis1)):
			lis3.append(lis1[i] + lis2[len(lis1) - i - 1])
		lis3.sort()
		print(lis3[0])


from math import ceil
t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	m = int(ceil(n / 2))
	a.sort()
	b.sort()
	c = []
	i = m - 1
	j = n - 1
	while i < n and j >= m - 1:
		c.append(a[i] + b[j])
		i += 1
		j -= 1
	print(min(c))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l1 = sorted(map(int, input().split()))[n // 2:]
	l2 = sorted(map(int, input().split()))[n // 2:]
	r3 = min((sum(i) for i in zip(l1, l2[::-1])))
	print(r3)


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)
	c = []
	for i in range(n // 2, n):
		c.append(a[i] + b[i - n // 2])
	print(min(c))


for _ in range(int(input())):
	n = int(input())
	boy = list(map(int, input().split(' ')))
	girl = list(map(int, input().split(' ')))
	boy.sort()
	girl.sort()
	x = n // 2
	a = girl[:x]
	b = girl[x:]
	b.sort(reverse=True)
	girl = a + b
	c = []
	for i in range(n):
		z = boy[i] + girl[i]
		c.append(z)
	c.sort()
	print(c[x])


import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7

def solve():
	n = int(input())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	ans = float('inf')
	for i in range(n // 2, n):
		ans = min(ans, a[i] + b[n - i - 1 + n // 2])
	return ans
for _ in range(int(input())):
	print(solve())


from numpy import inf
for _ in range(int(input())):
	n = int(input())
	brr = list(map(int, input().split()))
	grr = list(map(int, input().split()))
	if n == 1:
		print(brr[0] + grr[0])
		continue
	brr.sort()
	grr.sort()
	res = inf
	back = n - 1
	for i in range(n // 2, n):
		res = min(res, brr[i] + grr[back])
		back -= 1
	print(res)