You and your friend Ilya are participating in an individual programming contest consisting of multiple stages. A contestant can get between $0$ and $100$ points, inclusive, for each stage, independently of other contestants.

Points received by contestants in different stages are used for forming overall contest results. Suppose that $k$ stages of the contest are completed. For each contestant, $k - \lfloor \frac{k}{4} \rfloor$ stages with the highest scores are selected, and these scores are added up. This sum is the overall result of the contestant. (Here $\lfloor t \rfloor$ denotes rounding $t$ down.)

For example, suppose $9$ stages are completed, and your scores are $50, 30, 50, 50, 100, 10, 30, 100, 50$. First, $7$ stages with the highest scores are chosen — for example, all stages except for the $2$-nd and the $6$-th can be chosen. Then your overall result is equal to $50 + 50 + 50 + 100 + 30 + 100 + 50 = 430$.

As of now, $n$ stages are completed, and you know the points you and Ilya got for these stages. However, it is unknown how many more stages will be held. You wonder what the smallest number of additional stages is, after which your result might become greater than or equal to Ilya's result, at least in theory. Find this number!


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of completed stages.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 100$) — your points for the completed stages.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 100$) — Ilya's points for the completed stages.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print a single integer — the smallest number of additional stages required for your result to be able to become greater than or equal to Ilya's result.

If your result is already not less than Ilya's result, print $0$.


-----Examples-----

Input
5
1
100
0
1
0
100
4
20 30 40 50
100 100 100 100
4
10 20 30 40
100 100 100 100
7
7 59 62 52 27 31 55
33 35 50 98 83 80 64
Output
0
1
3
4
2


-----Note-----

In the first test case, you have scored $100$ points for the first stage, while Ilya has scored $0$. Thus, your overall result ($100$) is already not less than Ilya's result ($0$).

In the second test case, you have scored $0$ points for the first stage, while Ilya has scored $100$. A single stage with an opposite result is enough for both your and Ilya's overall scores to become equal to $100$.

In the third test case, your overall result is $30 + 40 + 50 = 120$, while Ilya's result is $100 + 100 + 100 = 300$. After three additional stages your result might become equal to $420$, while Ilya's result might become equal to $400$.

In the fourth test case, your overall result after four additional stages might become equal to $470$, while Ilya's result might become equal to $400$. Three stages are not enough.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Sorting

Greedy algorithms


Solutions:
def readline():
	return map(int, input().split())

def solve():
	n = int(input())
	a = sorted(readline())
	b = sorted(readline())
	q = n // 4
	sa = sum(a[q:])
	sb = sum(b[q:])
	k = 0
	while sa < sb:
		k += 1
		sa += 100
		if (n + k) % 4 == 0:
			sa -= a[q] if q < n else 100
			q += 1
		else:
			sb += b[q - k] if q >= k else 0
	print(k)

def main():
	t = int(input())
	for __ in range(t):
		solve()
main()


import sys
import math
input = sys.stdin.readline
imp = 'IMPOSSIBLE'
t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort(reverse=True)
	b = list(map(int, input().split(' ')))
	b.sort(reverse=True)
	bs = sum(b)
	kmax = n
	kmin = 0
	k = n // 2
	while kmin < kmax:
		top = n + k - math.floor((n + k) / 4)
		if top >= n:
			btop = bs
		else:
			btop = sum(b[:top])
		atop = k * 100 + sum(a[:top - k])
		if atop >= btop:
			kmax = k
			k = kmin + (kmax - kmin) // 2
		else:
			kmin = k + 1
			k = kmin + (kmax - kmin) // 2
	print(k)


import math
t = int(input())
for l in range(t):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	b = list(map(int, input().rstrip().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	k = n - n // 4
	sa = sum(a[:k])
	sb = sum(b[:k])
	if sa >= sb:
		print(0)
	else:
		count = 0
		while sa < sb:
			d = abs(sa - sb)
			tmp = math.ceil(d / 100)
			count += tmp
			k = n + count - (n + count) // 4
			if k > n:
				sb = sum(b)
			else:
				sb = sum(b[:k])
			if count >= k:
				sa = 100 * k
			else:
				sa = count * 100 + sum(a[:k - count])
		print(count)


def pursuit(n, a, b):
	k = n
	calc = k - k // 4
	a.sort(reverse=True)
	b.sort(reverse=True)
	scoreOfA = sum(a[:calc])
	scoreOfB = sum(b[:calc])
	if scoreOfA >= scoreOfB:
		return 0
	bl = calc
	al = calc - 1
	while scoreOfA < scoreOfB:
		k += 1
		if k % 4 == 0:
			scoreOfA += 100 - a[al]
			al -= 1
		else:
			scoreOfA += 100
			if bl >= n:
				pass
			else:
				scoreOfB += b[bl]
				bl += 1
	return k - n
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(pursuit(n, a, b))


from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().strip().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
from math import ceil
for _ in range(rn()):
	n = rn()
	a = sorted(rl())
	b = sorted(rl())
	low = 0
	high = n
	ans = float('inf')
	while low <= high:
		mid = (low + high) // 2
		take = ceil(3 * (n + mid) / 4)
		c = mid * 100 + sum(a[n - (take - mid):])
		d = sum(b[max(n - take, 0):])
		if c >= d:
			ans = min(ans, mid)
			high = mid - 1
		else:
			low = mid + 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	b = list(map(int, input().split()))
	b.sort(reverse=True)
	k = n - n // 4
	s1 = sum(a[0:k])
	s2 = sum(b[0:k])
	if s1 >= s2:
		print(0)
	else:
		index = k - 1
		nCopy = n
		while s1 < s2:
			n += 1
			if n % 4:
				s1 += 100
				if k < nCopy:
					s2 += b[k]
					k += 1
				continue
			sum1 = a[index]
			index -= 1
			s1 += 100 - sum1
		print(n - nCopy)


t = int(input())
for i in range(t):
	n = int(input())
	lst1 = list(map(int, input().split()))
	lst2 = list(map(int, input().split()))
	lst1.sort(reverse=True)
	lst2.sort(reverse=True)
	lst1 = lst1[:n - n // 4]
	c = 0
	sa = sum(lst1)
	sb = sum(lst2[:n - n // 4])
	cb = n - n // 4
	while True:
		if sa >= sb:
			break
		else:
			c += 1
			if (n + c) % 4 != 0:
				sa += 100
				if cb < n:
					sb += lst2[cb]
					cb += 1
			else:
				sa += 100 - lst1[-1]
				lst1.pop()
	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(reverse=True)
	b.sort(reverse=True)
	l = 0
	r = n + (sum(b) - sum(a)) // 100
	while l < r:
		mid = (l + r) // 2
		k = (mid + n) // 4
		if k > n:
			sm = (mid + n - k) * 100
		else:
			sm = mid * 100 + sum(a[:n - k])
		k = mid + n - k
		if sm >= sum(b[:min(k, n)]):
			r = mid
		else:
			l = mid + 1
	print(l)


import math

def isGood(mypoints, ilyapoints, numstages, numMore):
	removal = numstages // 4
	numZeroes = max(removal - numMore, 0)
	return sum(mypoints[removal:]) + numMore * 100 >= sum(ilyapoints[numZeroes:])

def pursuit(mypoints, ilyapoints, numstages):
	mypoints.sort()
	ilyapoints.sort()
	numMore = 0
	total = 0
	if isGood(mypoints, ilyapoints, numstages, numMore):
		return 0
	else:
		while not isGood(mypoints, ilyapoints, numstages, numMore):
			removal = numstages // 4
			numZeroes = max(removal - numMore, 0)
			howManyMore = sum(ilyapoints[numZeroes:]) - (sum(mypoints[removal:]) + numMore * 100)
			howManyMore = int(math.ceil(howManyMore / 100))
			numstages += howManyMore
			numMore += howManyMore
			total += howManyMore
		return total
t = int(input())
for i in range(t):
	n = int(input())
	mypoints = [int(x) for x in input().split()]
	ilyapoints = [int(x) for x in input().split()]
	print(pursuit(mypoints, ilyapoints, len(mypoints)))


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
inf = 10 ** 16
md = 10 ** 9 + 7

def solve():
	n = II()
	aa = LI()
	bb = LI()
	sa = [0]
	for a in sorted(aa, reverse=True):
		sa.append(sa[-1] + a)
	sb = [0]
	for a in sorted(bb, reverse=True):
		sb.append(sb[-1] + a)

	def ok(m):
		k = n + m - (n + m) // 4
		s = 100 * min(k, m) + sa[max(0, k - m)]
		t = sb[min(n, k)]
		return s >= t
	(l, r) = (-1, n)
	while l + 1 < r:
		m = (l + r) // 2
		if ok(m):
			r = m
		else:
			l = m
	print(r)
for testcase in range(II()):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	a.sort()
	b.sort()
	k = n // 4
	a_s = sum(a[k:])
	b_s = sum(b[k:])
	ans = 0
	j = k - 1
	while b_s > a_s:
		n += 1
		a_s += 100
		if n % 4 == 0:
			a_s -= a[k]
			k += 1
		elif j >= 0:
			b_s += b[j]
			j -= 1
		ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	m = n - n // 4
	a_score = sum(a[:m])
	b_score = sum(b[:m])
	n2 = n
	ja = m - 1
	jb = m
	while b_score > a_score:
		n2 += 1
		if n2 % 4 != 0:
			a_score += 100
			if jb < n:
				b_score += b[jb]
			jb += 1
		else:
			a_score += 100
			if ja >= 0:
				a_score -= a[ja]
			ja -= 1
	print(n2 - n)


for i in range(int(input())):
	n = int(input())
	l1 = sorted(list(map(int, input().split())))
	l2 = sorted(list(map(int, input().split())))
	a = int(n / 4)
	s1 = sum(l1) - sum(l1[:a])
	s2 = sum(l2) - sum(l2[:a])
	b = a - 1
	d = 0
	while s1 < s2:
		s1 += 100
		d += 1
		n += 1
		if b > -1:
			s2 += l2[b]
		b -= 1
		if n % 4 == 0 and a < n:
			s1 -= l1[a]
			a += 1
			if b > -2:
				b += 1
				s2 -= l2[b]
	print(d)


import sys
input = lambda : sys.stdin.readline()
int_arr = lambda : list(map(int, input().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().split())
get_int = lambda : map(int, input().split())
get_flo = lambda : map(float, input().split())
mod = 1000000007

def solve(n, a, b):
	a.sort(reverse=True)
	b.sort(reverse=True)
	k = n - n // 4
	atot = 0
	btot = 0
	for i in range(k):
		atot += a[i]
	for i in range(k):
		btot += b[i]
	ans = 0
	i = k
	j = k - 1
	m = n + 1
	while atot < btot:
		tmp = m - m // 4
		if k == tmp:
			if j >= 0:
				atot -= a[j]
			j -= 1
		else:
			if i < n:
				btot += b[i]
			i += 1
		k = tmp
		atot += 100
		ans += 1
		m += 1
	print(ans)
for _ in range(int(input())):
	n = int(input())
	a = sorted(int_arr())
	b = sorted(int_arr())
	solve(n, a, b)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	i = n - n // 4
	nc = n
	b.sort(reverse=True)
	a.sort(reverse=True)
	asum = sum(a[:i])
	bsum = sum(b[:i])
	bruh = i - 1
	c = 0
	z = i
	while asum < bsum:
		c += 1
		if n % 4 == 3:
			n += 1
			asum += 100
			if bruh > -1:
				asum -= a[bruh]
				bruh -= 1
			else:
				asum -= 100
		else:
			n += 1
			asum += 100
			if z < nc:
				bsum += b[z]
				z += 1
	print(c)


from sys import *
from math import *
input = lambda : stdin.readline()
int_arr = lambda : list(map(int, stdin.readline().strip().split()))
str_arr = lambda : list(map(str, stdin.readline().split()))
get_str = lambda : map(str, stdin.readline().strip().split())
get_int = lambda : map(int, stdin.readline().strip().split())
get_float = lambda : map(float, stdin.readline().strip().split())
mod = 1000000007
setrecursionlimit(1000)
for _ in range(int(input())):
	n = int(input())
	a = int_arr()
	b = int_arr()
	a.sort(reverse=True)
	b.sort(reverse=True)
	target = n - n // 4
	sum_a = sum(a[:target])
	sum_b = sum(b[:target])
	ind1 = target
	length = n
	if sum_a >= sum_b:
		print(0)
	else:
		ct = 0
		while sum_a < sum_b:
			sum_a += 100
			ct += 1
			n += 1
			if n % 4 == 0:
				target -= 1
				sum_a -= a[target]
			elif ind1 < length:
				sum_b += b[ind1]
				ind1 += 1
		print(ct)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	l = n - n // 4
	sa = sum(a[:l])
	sb = sum(b[:l])
	pointer = l - 1
	pointer_b = l
	c = 0
	i = n + 1
	while sb > sa:
		c += 1
		if i % 4 == 0:
			if pointer >= 0:
				sa -= a[pointer]
				sa += 100
				pointer -= 1
			else:
				i += 1
				continue
		else:
			sa += 100
			if pointer_b < n:
				sb += b[pointer_b]
				pointer_b += 1
		i += 1
	print(c)


for i in range(int(input())):
	size = int(input())
	my_arr = sorted(list(map(int, input().split())))
	his_arr = sorted(list(map(int, input().split())))
	count = 0
	leave = size // 4
	my_arr = my_arr[leave:]
	my_sum = sum(my_arr)
	his_sum = sum(his_arr[leave:])
	step = size % 4
	case = -1
	while my_sum < his_sum:
		count += 1
		step += 1
		my_sum += 100
		my_arr.append(100)
		if step % 4 == 0:
			case += 1
			my_sum -= my_arr[case]
		elif leave > 0:
			leave -= 1
			his_sum += his_arr[leave]
	print(count)


def main(n, a, b) -> int:
	include = n - n // 4
	a.sort(reverse=True)
	b.sort(reverse=True)
	score_a = sum(a[:include])
	score_b = sum(b[:include])
	included = include
	total_stages_till_now = n
	pointer_b = include
	pointer_a = include - 1
	while score_a < score_b:
		total_stages_till_now += 1
		include = total_stages_till_now - total_stages_till_now // 4
		if include > included:
			if pointer_b < n:
				score_b += b[pointer_b]
				pointer_b += 1
			score_a += 100
			included += 1
		elif pointer_a >= 0:
			score_a += 100 - a[pointer_a]
			pointer_a -= 1
		if pointer_b >= n and pointer_a < 0:
			required = (score_b - score_a + 99) // 100
			extra = 0
			if required > 0:
				if total_stages_till_now % 4 == 0:
					extra = 4 * required
				else:
					extra = total_stages_till_now % 4 + 4 * (required - 1)
			total_stages_till_now += extra
			break
	return total_stages_till_now - n
t = int(input())
ans = []
for i in range(t):
	N = int(input())
	a = [int(i) for i in input().split(' ')]
	b = [int(i) for i in input().split(' ')]
	ans.append(main(N, a, b))
for i in ans:
	print(i)


import sys
input = sys.stdin.readline
for nt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	c = c2 = n // 4
	s1 = sum(a) - sum(a[0:c])
	s2 = sum(b) - sum(b[0:c])
	ans = 0
	while s1 < s2:
		s1 += 100
		ans += 1
		if c != 0 and (n + ans) % 4 != 0:
			s2 += b[c - 1]
			c -= 1
		if (n + ans) % 4 == 0:
			s1 -= a[c2]
			c2 += 1
	print(ans)


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()
	k = n // 4
	x = sum(a[k:])
	y = sum(b[k:])
	j = k - 1
	ans = 0
	while x < y:
		n += 1
		x += 100
		if n % 4 == 0:
			x -= a[k]
			k += 1
		elif j >= 0:
			y += b[j]
			j -= 1
		ans += 1
	print(ans)


t = int(input())

def solve(n, A, B):
	A.sort()
	B.sort()
	k = int(n / 4)
	j = k - 1
	sumA = sum(A[k:])
	sumB = sum(B[k:])
	i = 0
	while sumA < sumB:
		i += 1
		n += 1
		sumA += 100
		if n % 4 == 0:
			k = int(n / 4) - 1
			sumA -= A[k]
			continue
		if j >= 0:
			sumB += B[j]
		j -= 1
	print(i)
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	solve(n, A, B)


from collections import Counter, deque
from math import *
mod = 1000000007

def isPrime(n):
	if n < 2:
		return False
	if n == 2 or n == 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(sqrt(n) + 1), 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	k = n // 4
	t1 = k
	t2 = k - 1
	temp = n
	cur1 = sum(a[k:])
	cur2 = sum(b[k:])
	if cur1 >= cur2:
		print(0)
		return
	count = 0
	for i in range(ceil(sum(b) / 100)):
		count += 1
		if (temp + count) % 4 == 0:
			cur1 -= a[t1]
			t1 += 1
			cur1 += 100
		else:
			cur1 += 100
			if t2 >= 0:
				cur2 += b[t2]
				t2 -= 1
		if cur1 >= cur2:
			print(count)
			return
t = int(input())
for _ in range(t):
	solve()


import math
t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	arr.sort(reverse=True)
	brr.sort(reverse=True)
	prefix_sum_arr = [arr[0]]
	for i in range(1, n):
		prefix_sum_arr += [prefix_sum_arr[-1] + arr[i]]
	prefix_sum_brr = [brr[0]]
	for i in range(1, n):
		prefix_sum_brr += [prefix_sum_brr[-1] + brr[i]]
	low = 0
	up = 100000 + 1
	ans = float('inf')
	while low <= up:
		mid = low + (up - low) // 2
		stages = n + mid - (n + mid) // 4
		my_score = 0
		her_score = 0
		if stages <= mid:
			my_score = 100 * stages
		else:
			my_score = 100 * mid + prefix_sum_arr[stages - mid - 1]
		if stages > n:
			her_score = prefix_sum_brr[-1]
		else:
			her_score = prefix_sum_brr[stages - 1]
		if my_score >= her_score:
			up = mid - 1
			ans = min(ans, mid)
		else:
			low = mid + 1
	print(ans)
while t:
	solve()
	t -= 1


def bin(I, Ilya, n):
	L = 0
	R = n
	while R - L != 1:
		M = (R + L) // 2
		k = n + M - (n + M) // 4
		l = k - M
		if M * 100 + sum(I[0:l]) >= sum(Ilya[0:k]):
			R = M
		else:
			L = M
	return R
t = int(input())
for p in range(t):
	n = int(input())
	I = list(map(int, input().split()))
	Ilya = list(map(int, input().split()))
	I.sort(reverse=True)
	Ilya.sort(reverse=True)
	k = n - n // 4
	if sum(I[0:k]) >= sum(Ilya[0:k]):
		print(0)
	else:
		for i in range(n):
			Ilya.append(0)
		print(bin(I, Ilya, n))


import sys
import math

def pro(arr, c):
	n = len(arr)
	arr.sort(reverse=True)
	c.sort(reverse=True)
	req = n - n // 4
	curr = sum(arr[:req])
	her = sum(c[:req])
	j = req - 1
	i = req - 1
	ans = 0
	while curr < her:
		n += 1
		if n % 4 == 0:
			if i - 1 >= 0:
				curr += 100 - arr[i]
				i -= 1
		else:
			curr += 100
			if j + 1 < len(c):
				j += 1
				her += c[j]
		ans += 1
	print(ans)
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = list(map(int, input().split()))
	pro(arr, c)


def smallNumAdd(n, my_point, iya_point):
	my_point.sort(reverse=True)
	iya_point.sort(reverse=True)
	add_step = 0
	total_stage = n
	step = n - n // 4
	(my_index, iya_index) = (step - 1, step)
	(my_score, iya_score) = (0, 0)
	for i in range(step):
		my_score += my_point[i]
		iya_score += iya_point[i]
	while my_score < iya_score:
		add_step += 1
		total_stage += 1
		new_stage = total_stage - total_stage // 4
		if new_stage == step:
			if my_index >= 0:
				my_score -= my_point[my_index]
				my_index -= 1
				my_score += 100
		else:
			step = new_stage
			my_score += 100
			if iya_index <= n - 1:
				iya_score += iya_point[iya_index]
				iya_index += 1
	print(add_step)
T = int(input())
for t in range(T):
	n = int(input())
	my_point = list(map(int, input().split()))
	iya_point = list(map(int, input().split()))
	smallNumAdd(n, my_point, iya_point)


def fun(a, b, n):
	k = n // 4
	a.sort()
	b.sort(reverse=True)
	idx_me = k
	me = sum(a[idx_me:])
	idx_you = n - k
	you = sum(b[:idx_you])
	r = 0
	while me < you:
		a.append(100)
		b.append(0)
		n += 1
		me += 100
		pre = k
		k = n // 4
		if k > pre:
			idx_me += 1
			me -= a[idx_me - 1]
		else:
			you += b[idx_you]
			idx_you += 1
		r += 1
	return r
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(fun(a, b, n))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	k = n - n // 4
	su_a = sum(a[0:k])
	su_b = sum(b[0:k])
	p1 = k - 1
	p2 = k
	i = n + 1
	c = 0
	while su_a < su_b:
		c += 1
		if i % 4 == 0:
			if p1 >= 0:
				su_a -= a[p1]
				su_a += 100
				p1 -= 1
		else:
			su_a += 100
			if p2 < n:
				su_b += b[p2]
				p2 += 1
		i += 1
	print(c)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	ap = [0] * (n + 1)
	bp = [0] * (n + 1)
	for i in range(n):
		ap[i + 1] = ap[i] + a[i]
		bp[i + 1] = bp[i] + b[i]
	l = -1
	r = n * 10
	while r - l > 1:
		c = (r + l) // 2
		k = n + c
		z = k - k // 4
		u = c * 100 + ap[z - c]
		v = bp[min(z, n)]
		if u >= v:
			r = c
		else:
			l = c
	print(r)
for i in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	my = list(map(int, input().split()))
	opp = list(map(int, input().split()))
	my.sort()
	opp.sort()
	(myScore, oppScore, ans) = (0, 0, 0)
	for i in range(n // 4, n):
		myScore += my[i]
		oppScore += opp[i]
	myId = n // 4 - 1
	oppId = n // 4 - 1
	while myScore < oppScore:
		n += 1
		if n % 4 == 0:
			myId += 1
			if myId < n:
				myScore -= my[myId]
			else:
				myScore -= 100
		else:
			if oppId >= 0:
				oppScore += opp[oppId]
			oppId -= 1
		myScore += 100
		ans += 1
	print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	a = sorted(map(int, input().split()))
	b = sorted(map(int, input().split()))
	num_exc = n // 4
	rem = n % 4
	sum_a = sum(a[num_exc:])
	sum_b = sum(b[num_exc:])
	a_pointer = num_exc
	b_pointer = num_exc - 1
	num_turns = 0
	while sum_a < sum_b:
		num_turns += 1
		sum_a += 100
		rem = (rem + 1) % 4
		if rem == 0:
			if a_pointer < n:
				sum_a -= a[a_pointer]
				a_pointer += 1
			else:
				sum_a -= 100
		elif b_pointer >= 0:
			sum_b += b[b_pointer]
			b_pointer -= 1
	print(num_turns)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr1.sort(reverse=True)
	arr2 = list(map(int, input().split()))
	arr2.sort(reverse=True)
	k = n - n // 4
	s1 = sum(arr1[0:k])
	s2 = sum(arr2[0:k])
	i = k - 1
	j = k
	res = 0
	m = n
	if s1 >= s2:
		print(0)
	else:
		while s1 < s2:
			res += 1
			m += 1
			s1 += 100
			if m % 4 != 0 and j < n:
				s2 += arr2[j]
				j += 1
			if m % 4 == 0 and i >= 0:
				s1 -= arr1[i]
				i -= 1
		print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = ans = 0
	ij = n // 4
	id1 = n // 4 - 1
	s1 = sum(a)
	s2 = sum(b)
	a.sort()
	b.sort()
	for i in range(ij):
		s1 -= a[i]
		s2 -= b[i]
	if s2 > s1:
		while s1 < s2:
			n += 1
			ans += 1
			if n % 4 == 0:
				s1 -= a[ij]
				ij += 1
				s1 += 100
			else:
				if id1 >= 0:
					s2 += b[id1]
					id1 -= 1
				s1 += 100
		print(ans)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	k = n // 4
	a.sort()
	b.sort()
	s1 = sum(a)
	s2 = sum(b)
	for i in range(k):
		s1 -= a[i]
		s2 -= b[i]
	if s1 >= s2:
		print(0)
	else:
		m = k
		q = k - 1
		c = n
		z = 0
		ans = 0
		while True:
			if s1 >= s2:
				break
			s1 += 100
			z += 1
			if q >= 0:
				s2 += b[q]
				q -= 1
			c += 1
			if c // 4 > k:
				k += 1
				s1 -= a[m]
				m += 1
				if z < k:
					s2 -= b[q + 1]
					q += 1
			ans += 1
		print(ans)


tests = int(input())
for _ in range(tests):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	k = n - n // 4
	ans = 0
	i = k - 1
	j = k
	curr_a = sum(a[:k])
	curr_b = sum(b[:k])
	while curr_a < curr_b:
		ans += 1
		curr_a += 100
		if i >= 0 and (ans + n) % 4 == 0:
			curr_a -= a[i]
			i -= 1
		elif (ans + n) % 4 == 0 and i < 0:
			curr_a -= 100
		if j < len(b) and (not (ans + n) % 4 == 0):
			curr_b += b[j]
			j += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	l = list(map(int, input().split()))
	m.sort(reverse=True)
	l.sort(reverse=True)
	c = 0
	k = n - n // 4
	sm = sum(m[:k])
	sl = sum(l[:k])
	while sm < sl:
		n += 1
		sm += 100
		if n % 4 == 0:
			sm -= m[n - n // 4 - 1 - c]
		elif n - n // 4 <= len(l):
			sm -= l[n - n // 4 - 1]
		c += 1
	print(c)


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=True)
	a2.sort(reverse=True)
	k = n - n // 4
	s1 = sum(a1[:k])
	s2 = sum(a2[:k])
	i = k - 1
	j = k
	c = 0
	m = n
	if s1 >= s2:
		print(0)
	else:
		while s2 > s1:
			c = c + 1
			m = m + 1
			s1 = s1 + 100
			if m % 4 != 0 and j < n:
				s2 = s2 + a2[j]
				j = j + 1
			elif m % 4 == 0 and i >= 0:
				s1 = s1 - a1[i]
				i = i - 1
		print(c)


I = lambda : map(int, input().split())
for _ in [0] * int(input()):
	n = int(input())
	(a, b) = (list(I()), list(I()))
	a = sorted(a)
	b = sorted(b)
	i = 1
	da = {}
	da[0] = 0
	db = {}
	db[0] = 0
	k = 0
	for (x, y) in zip(a, b):
		da[i] = x + da[i - 1]
		db[i] = y + db[i - 1]
		i = i + 1
	delta = da[n] - da[n // 4] - (db[n] - db[n // 4])
	if delta < 0:
		i = 1
		j = n
		jj = da[n] - db[n]
		while j >= i and i < n + 1 and (j > 0):
			k = (i + j) // 2
			yy = (k + n) // 4
			delta = jj - da[yy] + 100 * k
			if yy > k:
				delta = delta + db[yy - k]
			if delta == 0:
				print(k)
				break
			elif delta < 0:
				i = k + 1
			else:
				j = k - 1
		if delta < 0:
			print(k + 1)
		elif delta > 0:
			print(k)
	else:
		print(0)


def main():
	a = int(input())
	for i in range(a):
		b = int(input())
		m = sorted(map(int, input().split()))
		m1 = sorted(map(int, input().split()))
		sm = 0
		sm1 = 0
		m_res = [0]
		m1_res = [0]
		for j in range(b):
			m_res.append(m_res[-1] + m[j])
			m1_res.append(m1_res[-1] + m1[j])
			sm += m[j]
			sm1 += m1[j]
		k = b // 4
		d = 0
		while sm - m_res[k] < sm1 - m1_res[k - d if k - d > 0 else 0]:
			d += 1
			sm += 100
			k = (b + d) // 4
		print(d)
main()


import os
import random
from sys import stdin, stdout
random.seed()

def read():
	return stdin.readline().strip()

def read_int():
	return [int(i) for i in read().split()]

def write(s):
	stdout.write(s)

def cal(a, v):
	n = len(a)
	if v - v // 4 <= v - n:
		return (v - v // 4) * 100
	else:
		return (v - n) * 100 + a[n - v // 4 - 1]
for _ in range(int(read())):
	(n,) = read_int()
	a = read_int()
	b = read_int()
	a.sort(reverse=True)
	b.sort(reverse=True)
	for i in range(1, n):
		a[i] += a[i - 1]
		b[i] += b[i - 1]
	if a[n - 1 - n // 4] >= b[n - 1 - n // 4]:
		print(0)
	else:
		add = 262144
		u = n
		while add:
			v = u + add
			if cal(a, v) < b[min(n, v - v // 4) - 1]:
				u += add
			add >>= 1
		print(u + 1 - n)


from math import sqrt, ceil, floor
import sys
import heapq as h
from collections import Counter, deque
from collections import defaultdict as dd

def foo(x):
	x = 0
t = int(input())
for tt in range(t):
	n = int(input())
	inn = n + 1 - 1
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	k = n - n // 4
	a = a[:k]
	A = sum(a)
	h.heapify(a)
	B = sum(b[:k])
	b = [-x for x in b[k:]]
	h.heapify(b)
	steps = 0
	while A < B:
		steps += 1
		n += 1
		if n % 4:
			A += 100
		elif a:
			x = h.heappop(a)
			A -= x
			A += 100
		if b and n % 4:
			x = -h.heappop(b)
			B += x
		else:
			pass
	print(steps)


def top_count(k):
	return k - k // 4
t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(map(int, input().split()), reverse=True)
	b = sorted(map(int, input().split()), reverse=True)
	cur_count = top_count(n)
	top_a = a[:cur_count]
	top_b = b[:cur_count]
	sum_a = sum(top_a)
	sum_b = sum(top_b)
	i = 0
	while True:
		n += 1
		if sum_a >= sum_b:
			break
		new_count = top_count(n)
		sum_a += 100
		if new_count == cur_count:
			sum_a -= top_a.pop()
		else:
			db = b[new_count - 1] if new_count <= len(b) else 0
			sum_b += db
		i += 1
		cur_count = new_count
	print(i)


import math
import heapq
t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	cura = 0
	curb = 0
	a.sort(reverse=True)
	b.sort(reverse=True)
	ori = n
	k = n - n // 4
	for i in range(k):
		cura += a[i]
		curb += b[i]
	if cura >= curb:
		print(0)
		continue
	save = []
	i = k - 1
	j = k
	while cura < curb:
		n += 1
		if n % 4 > 0:
			if j < len(b):
				curb += b[j]
				j += 1
			cura += 100
		else:
			cura += 100
			cura -= a[i]
			i -= 1
	print(n - ori)
1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	sa = [0 for _ in range(n + 1)]
	sb = [0 for _ in range(n + 1)]
	for i in range(1, n + 1):
		sa[i] = sa[i - 1] + a[i - 1]
		sb[i] = sb[i - 1] + b[i - 1]
	st = n - n // 4
	l = n
	r = int(1000000000.0)
	while l <= r:
		mid = (l + r) // 2
		tot = mid - mid // 4
		if mid - n >= tot:
			ra = tot * 100
		else:
			ra = (mid - n) * 100 + sa[tot - mid + n]
		if tot > n:
			rb = sb[n]
		else:
			rb = sb[tot]
		if ra >= rb:
			r = mid - 1
		else:
			l = mid + 1
	print(r - n + 1)


def check(suffixA, suffixB, m):
	k = n + m - (n + m) // 4
	vb = suffixB[0] if k >= n else suffixB[n - k]
	if k > m:
		va = m * 100
		k -= m
		assert k <= n
		if k != 0:
			va += suffixA[n - k]
	else:
		va = k * 100
	return va >= vb
T = int(input())
for _ in range(T):
	n = int(input())
	A = [int(e) for e in input().split(' ')]
	A.sort()
	B = [int(e) for e in input().split(' ')]
	B.sort()
	k = n - n // 4
	(sA, sB) = (sum(A[n - k:]), sum(B[n - k:]))
	suffixA = [0] * n
	suffixA[-1] = A[-1]
	for i in range(n - 2, -1, -1):
		suffixA[i] = suffixA[i + 1] + A[i]
	suffixB = [0] * n
	suffixB[-1] = B[-1]
	for i in range(n - 2, -1, -1):
		suffixB[i] = suffixB[i + 1] + B[i]
	if sA >= sB:
		print(0)
	else:
		(l, h) = (0, 10 ** 7)
		while l < h:
			m = (l + h) // 2
			if check(suffixA, suffixB, m):
				h = m
			else:
				l = m + 1
		print(l if check(suffixA, suffixB, l) else h)


import math
import heapq
import string
from collections import deque
import sys
input = sys.stdin.readline
S = lambda : input()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
for _ in range(I()):
	n = I()
	y = L()
	l = L()
	n1 = len(l)
	y.sort()
	l.sort()
	k = n - n // 4
	j = n - k
	i = n - k - 1
	s = sum(y[j:])
	t = sum(l[j:])
	while s < t:
		n += 1
		if n % 4 == 0:
			if j < n1:
				s += 100 - y[j]
				j += 1
		else:
			s += 100
			if i >= 0:
				t += l[i]
				i -= 1
	print(n - n1)


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()
	v1 = n - n // 4
	s1 = sum(a[n - v1:])
	s2 = sum(b[n - v1:])
	if s1 >= s2:
		print(0)
	else:
		cnt = 0
		flg = 0
		while 1:
			cnt += 1
			a.append(100)
			v2 = n + cnt - (n + cnt) // 4
			if v2 > v1:
				v1 = v2 + 0
				if v1 > n:
					s1 += 100
					s2 += 0
					break
				else:
					s1 += 100
					s2 += b[n - v1]
					if s1 >= s2:
						flg = 1
						break
			else:
				s1 += 100 - a[n + cnt - v1 - 1]
				if s1 >= s2:
					flg = 1
					break
		if flg == 1 or s1 >= s2:
			print(cnt)
		else:
			while 1:
				cnt += 1
				a.append(100)
				v2 = n + cnt - (n + cnt) // 4
				if v2 > v1:
					v1 = v2 + 0
					s1 += 100
					if s1 >= s2:
						break
				else:
					s1 += 100 - a[n + cnt - v1 - 1]
					if s1 >= s2:
						break
			print(cnt)


for _ in range(int(input())):
	n = int(input())
	n1 = n
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	res = 0
	t = n - n // 4
	s1 = sum(a[:t])
	s2 = sum(b[:t])
	i = t - 1
	j = t
	while s1 < s2:
		n += 1
		if n % 4 == 0:
			if i >= 0:
				s1 += 100 - a[i]
				i -= 1
		else:
			s1 += 100
			if j < n1:
				s2 += b[j]
				j += 1
		res += 1
	print(res)


import math
t = int(input())
for testcase in range(t):
	n = int(input())
	n_ = n
	a = input().split()
	b = input().split()
	for i in range(n):
		a[i] = int(a[i])
		b[i] = int(b[i])
	a = sorted(a, reverse=True)
	b = sorted(b, reverse=True)
	ptr = n - n // 4
	ptr_ = ptr - 1
	s1 = sum(a[:ptr])
	s2 = sum(b[:ptr])
	while s1 < s2:
		n += 1
		if n % 4 == 0:
			if ptr_ >= 0:
				s1 += 100 - a[ptr_]
				ptr_ -= 1
			continue
		else:
			s1 += 100
			if ptr < n_:
				s2 += b[ptr]
				ptr += 1
	print(n - n_)


import math as m
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = n - n // 4
	a.sort()
	b.sort()
	aa = sum(a[n - x:])
	bb = sum(b[n - x:])
	c = b[:n - x]
	c = c[::-1]
	w = 0
	y = 0
	r = n - x
	while aa < bb:
		n += 1
		x = n - n // 4
		if n % 4 != 0:
			aa += 100
			if y < len(c):
				bb += c[y]
				y += 1
		else:
			aa += 100
			aa -= a[r]
			r += 1
		w += 1
	print(w)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = n - n // 4
	a.sort(reverse=True)
	b.sort(reverse=True)
	sa = sum(a[:c])
	sb = sum(b[:c])
	ans = 0
	while sa < sb:
		n += 1
		sa += 100
		if n % 4 == 0:
			sa -= a[n - n // 4 - ans - 1]
		elif n - n // 4 <= len(b):
			sb += b[n - n // 4 - 1]
		ans += 1
	print(ans)


def read_int():
	return int(input())

def read_ints():
	return map(int, input().split(' '))
t = read_int()
for case_num in range(t):
	n = read_int()
	a = list(read_ints())
	b = list(read_ints())
	a.sort(reverse=True)
	b.sort(reverse=True)
	sa = [0] * (n + 1)
	sb = [0] * (n + 1)
	for i in range(1, n + 1):
		sa[i] = sa[i - 1] + a[i - 1]
		sb[i] = sb[i - 1] + b[i - 1]
	l = 0
	r = n * 3
	while l <= r:
		mid = (l + r) // 2
		take = n + mid - (n + mid) // 4
		raw = max(0, take - mid)
		ca = sa[raw] + 100 * (take - raw)
		cb = sb[min(n, take)]
		if ca >= cb:
			r = mid - 1
		else:
			l = mid + 1
	print(l)


from sys import stdin
from heapq import heappush, heappop, heappushpop, heapreplace, heapify
from math import ceil
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	b = list(map(int, stdin.readline().split()))
	heapify(a)
	heapify(b)
	temp = []
	for i in range(n // 4):
		heappop(a)
		heappush(temp, -1 * heappop(b))
	sa = sum(a)
	sb = sum(b)
	ans1 = n
	while sa < sb:
		sa += 100
		ans1 += 1
		heappush(a, 100)
		if ans1 % 4 == 0:
			sa -= heappop(a)
		elif len(temp):
			sb += -1 * heappop(temp)
	print(ans1 - n)


t = int(input())
for _ in range(t):
	n = int(input())
	ar = sorted(list(map(int, input().split())))
	ilya = sorted(list(map(int, input().split())))
	con = n // 4
	target = sum(ilya[con:])
	s = sum(ar[con:])
	skipped = con
	skipped2 = con - 1
	if target <= s:
		print(0)
	else:
		c = 0
		while True:
			c += 1
			n += 1
			if n % 4 == 0:
				s += 100
				s -= ar[skipped]
				skipped += 1
			else:
				s += 100
				if skipped2 >= 0:
					target += ilya[skipped2]
					skipped2 -= 1
			if target <= s:
				print(c)
				break


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	b = list(map(int, input().split()))
	b = sorted(b)
	o = n
	res = o // 4
	last = res
	id1 = res - 1
	id2 = id1
	s1 = 0
	s2 = 0
	for j in range(res, n):
		s1 += a[j]
		s2 += b[j]
	c = 0
	while s1 < s2:
		c += 1
		o += 1
		res = o // 4
		if res != last:
			id1 += 1
			if id1 < n:
				s1 -= a[id1]
			s1 += 100
		else:
			s1 += 100
			if id2 > -1:
				s2 += b[id2]
				id2 -= 1
		last = res
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = list(map(int, input().split()))
	l.sort(reverse=True)
	l1.sort(reverse=True)
	a = sum(l[:n - n // 4])
	b = sum(l1[:n - n // 4])
	cnt = 0
	while b > a:
		n += 1
		a += 100
		if n % 4 == 0:
			a -= l[n - n // 4 - 1 - cnt]
		elif n - n // 4 <= len(l1):
			b += l1[n - n // 4 - 1]
		cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	n = int(input())
	yourpoints = [int(x) for x in input().split()]
	theirpoints = [int(x) for x in input().split()]
	yourpoints.sort(reverse=True)
	theirpoints.sort(reverse=True)
	temp = n - n // 4
	location = temp
	yoursum = 0
	theirsum = 0
	for i in range(temp):
		yoursum += yourpoints[i]
		theirsum += theirpoints[i]
	step = 0
	if yoursum >= theirsum:
		print(step)
	else:
		while yoursum < theirsum:
			step += 1
			previous = temp
			n += 1
			temp = n - n // 4
			if temp == previous:
				yoursum -= yourpoints[location - 1]
				location -= 1
			elif temp <= len(theirpoints):
				theirsum += theirpoints[temp - 1]
			yoursum += 100
			theirsum
		print(step)


casos = int(input())

def puntaje(lista, n):
	q = 0
	for i in range(n):
		if i >= n // 4:
			q += lista[i]
	return q
while casos > 0:
	n = int(input())
	rondas = 0
	DIE = input().split()
	DCC = input().split()
	DIE = list(map(int, DIE))
	DCC = list(map(int, DCC))
	DCC.sort()
	DIE.sort()
	x = puntaje(DCC, n)
	y = puntaje(DIE, n)
	suma = x - y
	r1 = n // 4
	r3 = n // 4
	while suma > 0:
		n += 1
		rondas += 1
		if n % 4 == 0:
			y += 100 - DIE[r1]
			r1 += 1
		else:
			y += 100
			if r3 > 0:
				r3 -= 1
				x += DCC[r3]
		suma = x - y
	casos -= 1
	print(rondas)


for i in range(int(input())):
	n = int(input())
	arr1 = sorted(list(map(int, input().split(' '))))
	arr2 = sorted(list(map(int, input().split(' '))), reverse=True)
	a = n - int(n / 4)
	b = a
	count = 0
	sm1 = sum(arr1[-b:])
	sm2 = sum(arr2[:b])
	if sm1 >= sm2:
		print(count)
	else:
		while sm1 < sm2:
			n += 1
			arr1.append(100)
			arr2.append(0)
			sm1 += 100
			a = n - int(n / 4)
			if a == b:
				sm1 -= arr1[-b - 1]
			else:
				sm2 += arr2[b]
			b = a
			count += 1
		print(count)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
sys.setrecursionlimit(depth)
from math import inf

def scoreA(k):
	if n <= k // 4:
		return (k - k // 4) * 100
	return (k - n) * 100 + a[n - k // 4]

def scoreB(k):
	return b[min(k - k // 4, n)]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	for i in range(1, n):
		a[i] += a[i - 1]
		b[i] += b[i - 1]
	a = [0] + a
	b = [0] + b
	(lo, hi, ans) = (n, 1000000000, inf)
	while lo <= hi:
		mid = (lo + hi) // 2
		if scoreA(mid) >= scoreB(mid):
			hi = mid - 1
			ans = min(ans, mid)
		else:
			lo = mid + 1
	print(ans - n)


import math
t = int(input())
for case 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()
	aSum = 0
	bSum = 0
	for i in range(n // 4, n):
		aSum += a[i]
		bSum += b[i]
	result = 0
	diff = aSum - bSum
	aPtr = n // 4
	bPtr = n // 4
	while diff < 0:
		if n % 4 != 3:
			bPtr -= 1
			bI = b[bPtr] if bPtr >= 0 else 0
			diff += 100 - bI
		else:
			aI = a[aPtr] if aPtr < n - result else 100
			diff += 100 - aI
			aPtr += 1
		n += 1
		result += 1
	print(result)


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())), reverse=True)
	b = sorted(list(map(int, input().split())), reverse=True)
	xa = sum(a[:n - int(n / 4)])
	xb = sum(b[:n - int(n / 4)])
	r = 0
	while xb > xa:
		n += 1
		xa += 100
		if n % 4 == 0:
			xa -= a[n - int(n / 4) - 1 - r]
		elif n - int(n / 4) <= len(b):
			xb += b[n - int(n / 4) - 1]
		r += 1
	print(r)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b.sort(key=lambda x: -x)
	a.sort()
	x = n - n // 4
	sa = sum(a[-x:])
	sb = sum(b[:x])
	if sa >= sb:
		print(0)
		continue
	an = 0
	while sa < sb:
		an += 1
		n += 1
		y = x
		x = n - n // 4
		a.append(100)
		b.append(0)
		if y == x:
			sa += 100
			sa -= a[-x - 1]
		else:
			sa += 100
			sb += b[x - 1]
	print(an)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ll = list(map(int, input().split()))
	l.sort()
	ll.sort()
	bob = 0
	llya = 0
	xx = n - n // 4
	c = 0
	q = n
	for i in range(n - 1, -1, -1):
		bob += l[i]
		llya += ll[i]
		c += 1
		if c == xx:
			break
	c = i - 1
	ind = i
	ans = 0
	while llya > bob:
		q += 1
		ans += 1
		ww = q - q // 4
		if q % 4 == 0:
			if ind < n:
				bob -= l[ind]
				bob += 100
				ind += 1
			continue
		elif c < 0:
			bob += 100
		else:
			bob += 100
			llya += ll[c]
			c -= 1
		xx = ww
	print(ans)


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)
	l = n // 4
	pl = n // 4
	x = sum(a[n // 4:])
	y = 0
	for j in range(n - l):
		y += b[j]
	yp = n - l
	ans = 0
	while x < y:
		ans += 1
		a.append(100)
		b.append(0)
		n += 1
		cl = n // 4
		x += 100
		y += b[yp]
		if cl > l:
			x -= a[pl]
			pl += 1
			l = cl
			y -= b[yp]
		else:
			yp += 1
	print(ans)


t = int(input())
for task in range(t):
	n = int(input())
	stageM = list(map(int, input().split()))
	stageE = list(map(int, input().split()))
	stageM.sort()
	stageE.sort()
	edgeM = edgeE = n // 4
	scoreM = scoreE = 0
	for i in range(edgeM, n):
		scoreM += stageM[i]
		scoreE += stageE[i]
	res = 0
	stages = n
	while scoreM < scoreE:
		stages += 1
		res += 1
		if stages % 4 == 0:
			edgeM += 1
			if edgeM < n + 1:
				scoreM = scoreM + 100 - stageM[edgeM - 1]
		else:
			scoreM += 100
			edgeE -= 1
			if edgeE >= 0:
				scoreE += stageE[edgeE]
	print(res)


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 = n - n // 4
	(l, h) = (n - c, n)
	s1 = sum(a[l:h])
	s2 = sum(b[:c])
	ans = 0
	while s1 < s2:
		a.append(100)
		b.append(0)
		n += 1
		diff = n - n // 4
		if c == diff:
			s1 = s1 - a[l] + 100
			l += 1
		else:
			s1 += 100
			s2 += b[diff - 1]
		c = diff
		ans += 1
	print(ans)


def isHigh(val, ti=False):
	turns = val - val // 4
	huns = min(val - n, turns)
	rem = turns - huns
	c1 = huns * 100 + s1[rem]
	tmp2 = min(n, turns)
	c2 = s2[tmp2]
	return c1 >= c2

def bs(l, r):
	mid = (l + r) // 2
	if isHigh(mid) and (not isHigh(mid - 1)):
		return mid
	if isHigh(mid):
		return bs(l, mid - 1)
	else:
		return bs(mid + 1, r)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	arr.sort(reverse=True)
	brr.sort(reverse=True)
	s1 = [0]
	s2 = [0]
	t1 = 0
	t2 = 0
	for i in range(n):
		t1 += arr[i]
		t2 += brr[i]
		s1.append(t1)
		s2.append(t2)
	if isHigh(n):
		print(0)
	else:
		ans = bs(n + 1, 2 * n)
		print(ans - n)


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	k = n - n // 4
	l1.sort()
	l2.sort()
	mx1 = 0
	mx2 = 0
	for i in range(n - 1, n - k - 1, -1):
		mx1 += l1[i]
		mx2 += l2[i]
	if mx1 >= mx2:
		print(0)
	else:
		count = 0
		tmp1 = k
		i1 = n - k
		i2 = n - k - 1
		n1 = n
		while mx1 < mx2:
			n += 1
			tmp2 = n - n // 4
			count += 1
			if tmp2 == tmp1 and i1 < n1:
				mx1 -= l1[i1]
				mx1 += 100
				i1 += 1
				tmp1 = tmp2
				continue
			elif tmp2 == tmp1:
				continue
			if i2 >= 0:
				mx2 += l2[i2]
				i2 -= 1
			mx1 += 100
			tmp1 = tmp2
		print(count)


R = lambda : sorted(map(int, input().split()))
for _ in [0] * R()[0]:
	(n,) = R()
	m = n
	a = R()
	b = R()
	s = t = 0
	for (x, y) in [*zip(a, b)][n // 4:]:
		s += x
		t += y
	a += [100] * n
	b = [0] * n + b
	while s < t:
		k = m // 4
		m += 1
		s += 100 - (m % 4 < 1) * a[k]
		t += m % 4 and b[k - m]
	print(m - n)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	x = 0
	y = 0
	t = n - n // 4
	for i in range(t):
		x = x + a[i]
		y = y + b[i]
	i = 1
	j = t
	while x < y:
		k = n + i
		l = k - k // 4
		x = x + 100
		if k % 4 == 0:
			if t >= 0:
				x = x - a[t - 1]
				t = t - 1
			else:
				x = x - 100
		if l <= n:
			if k % 4 != 0:
				y = y + b[j]
				j = j + 1
		i = i + 1
	print(i - 1)


j = int(input())
while j > 0:
	n = int(input())
	l = [int(i) for i in input().split(' ')]
	L = [int(i) for i in input().split(' ')]
	l.sort()
	l.reverse()
	L.sort()
	L.reverse()
	x = n - n // 4
	s = sum(l[0:x])
	S = sum(L[0:x])
	if s >= S:
		print(0)
	else:
		k = n + 1
		a = 1
		b = 1
		while k > 0:
			if k % 4 == 0:
				s = s - l[x - a]
				a = a + 1
				if s + (k - n) * 100 >= S:
					print(k - n)
					break
			elif n < x + b:
				if s + (k - n) * 100 >= S:
					print(k - n)
					break
			else:
				S = S + L[x - 1 + b]
				b = b + 1
				if s + (k - n) * 100 >= S:
					print(k - n)
					break
			k = k + 1
	j = j - 1


for _ in range(int(input())):
	n = int(input())
	a = sorted([int(i) for i in input().split()])
	b = sorted([int(i) for i in input().split()])
	p = n // 4
	s1 = sum(a[p:])
	s2 = sum(b[p:])
	c = 0
	minus = 0
	sumb = sum(b)
	a = [0] + a + [0]
	b = [0] + b + [0]
	count = 0
	if s1 >= s2:
		print(0)
		continue
	while s1 < s2:
		c += 1
		s1 += 100
		s2 += b[max(0, p - c + 1 + count)]
		if (n + c) % 4 == 0:
			minus += 1
			s1 -= a[min(n, p + minus)]
			s2 -= b[max(0, p - c + 1 + count)]
			v = True
			count += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	n4 = n
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	sa = 0
	sb = 0
	n1 = n - n // 4
	n3 = n1
	a = a[::-1]
	b = b[::-1]
	for i in range(n1):
		sa += a[i]
		sb += b[i]
	p = n1 - 1
	q = n1 - 1
	while sa < sb:
		n += 1
		n2 = n - n // 4
		if n1 == n2:
			if p >= 0:
				sa += 100 - a[p]
				p -= 1
			continue
		n1 = n2
		q += 1
		if q >= n4:
			b += [0]
		sa += 100
		sb += b[q]
	print(n - n4)


import collections
t = int(input())
for T in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	orig = n
	a.sort(reverse=True)
	b.sort(reverse=True)
	k = n - n // 4
	sa = 0
	sb = 0
	for i in range(k):
		sa += a[i]
		sb += b[i]
	nstart = k
	remover = k - 1
	if sa >= sb:
		print(0)
	else:
		ans = 0
		while sb > sa:
			ans += 1
			n += 1
			if nstart <= orig - 1:
				sb += b[nstart]
				nstart += 1
			else:
				b.append(0)
				nstart += 1
				sb += 0
			sa += 100
			if n % 4 == 0:
				nstart -= 1
				sb -= b[nstart]
				sa -= a[remover]
				remover -= 1
		print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	a.sort(reverse=True)
	b.sort(reverse=True)
	for i in range(1, n):
		a[i] += a[i - 1]
		b[i] += b[i - 1]
	(l, r) = (-1, 10 ** 9)
	while l + 1 < r:
		m = (l + r) // 2
		g = n + m - (n + m) // 4
		rem = g - m - 1
		if rem >= n:
			rem = n - 1
		s2 = b[min(n - 1, g - 1)]
		s1 = 100 * min(m, g)
		if rem >= 0:
			s1 += a[rem]
		if s1 >= s2:
			r = m
		else:
			l = m
	print(r)


from collections import deque
t = int(input())
for q in range(t):
	n = int(input())
	my_arr = list(map(int, input().split()))
	il_arr = list(map(int, input().split()))
	my_arr.sort(reverse=True)
	il_arr.sort(reverse=True)
	sub = n - n // 4
	my_var = deque()
	sum_kol = 0
	my_sum = il_sum = 0
	for i in range(sub):
		my_var.append(my_arr[i])
		my_sum += my_arr[i]
		il_sum += il_arr[i]
		sum_kol += 1
	count = 0
	while il_sum > my_sum:
		count += 1
		sub = n + count - (n + count) // 4
		if sub > len(my_var):
			my_sum += 100
			my_var.appendleft(100)
			if sub <= n:
				il_sum += il_arr[sub - 1]
		else:
			last = my_var.pop()
			my_var.appendleft(100)
			my_sum += 100 - last
	print(count)


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(reverse=True)
	acum = a[:]
	bcum = b[:]
	for j in range(1, n):
		acum[j] = acum[j - 1] + acum[j]
		bcum[j] = bcum[j - 1] + bcum[j]
	asum = acum[n - n // 4 - 1]
	am = n - n // 4 - 1
	bsum = bcum[n - n // 4 - 1]
	bm = n - n // 4 - 1
	c = 0
	if asum >= bsum:
		print(0)
	else:
		nt = n
		while c == 0:
			nt += 1
			if nt % 4 == 0:
				asum += 100 - a[am]
				am -= 1
			else:
				asum += 100
				if bm < n - 1:
					bm += 1
					bsum = bcum[bm]
			if asum >= bsum:
				print(nt - n)
				c = 420691337


import math
t = int(input())
for _ in range(t):
	n = int(input())
	Me = list(map(int, input().split(' ')))
	Li = list(map(int, input().split(' ')))
	limit = n - n // 4
	Me.sort(reverse=True)
	me_pop = [Me[0]]
	for i in range(1, n):
		me_pop.append(me_pop[i - 1] + Me[i])
	Li.sort(reverse=True)
	lipop = [Li[0]]
	for i in range(1, n):
		lipop.append(lipop[i - 1] + Li[i])
	x = me_pop[limit - 1]
	y = lipop[limit - 1]
	count = 0
	while x < y:
		count += 1
		limit = n + count - (n + count) // 4
		x = me_pop[limit - count - 1] + count * 100
		if limit < n:
			y = lipop[limit - 1]
		else:
			y = lipop[-1]
	print(count)