Chef's exam is near. There is a total of M subjects in his syllabus. Each subject consists of several topics. However, the questions will be set only from N topics. These topics are numbered 1 through N. The i^{th} topic belongs to C_{i}^{th} subject and takes T_{i} hours to cover.

Chef has only K hours left before the exam and wants to score the maximum marks. If Chef covers x_{1} number of topics of the 1^{st} subject, x_{2} number of topics of the 2^{nd} subject, and so on upto  x_{M} number of topics of the M^{th} subject in the remaining K hours, he will get a total of \lceil \frac{x_{1}}{2} \ \rceil + \lceil \frac{x_{2}}{2} \ \rceil + \cdots + \lceil \frac{x_{M}}{2} \ \rceil marks in the exam. So Chef chooses the topics optimally.

Determine the maximum possible marks Chef can score in the exam.

Note: \lceil x \rceil : Returns the smallest integer that is greater than or equal to x (i.e  rounds up to the nearest integer). For example, \lceil 1.5 \rceil = 2, \lceil 5 \rceil = 5.

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

- The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- Each test case contains three lines of input.
- The first line of each test case contains three space-separated integers N, M, K.
- The second line contains N space-separated integers C_{1}, C_{2}, \dots, C_{N}.
- The third line contains N space-separated integers T_{1}, T_{2}, \dots, T_{N}.

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

For each test case, print a single line containing one integer - the maximum marks Chef can score.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ N$
$1 ≤ K ≤ 10^{9}$
$1 ≤ C_{i} ≤ M$
$1 ≤ T_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $5\cdot10^{5}$.

----- Sample Input 1 ------ 
3
3 2 2
1 1 2
1 1 2
4 3 2
1 1 2 2
1 1 2 1
5 3 10
1 1 1 2 3
1 5 2 5 1
----- Sample Output 1 ------ 
1
2
3

----- explanation 1 ------ 
Test case $1$: Chef covers the $1^{st}$ and $2^{nd}$ topic in $1 + 1 = 2$ hours. Both topics belongs to $1^{st}$ subject. He does not cover any topic of the second subject. By doing so, Chef gets $\lceil \frac{2}{2} \ \rceil + \lceil \frac{0}{2} \ \rceil$ = $\lceil \ 1 \ \rceil + \lceil \ 0 \ \rceil = 1$ marks.

Test case $2$: Chef covers the $1^{st}$ topic which belongs to the first subject and $4^{th}$ topic which belongs to the second subject in $1 + 1 = 2$ hours. There is no topic from the third subject. So Chef gets $\lceil \frac{1}{2} \ \rceil + \lceil \frac{1}{2} \ \rceil$ = $\lceil \ 0.5 \ \rceil + \lceil \ 0.5 \ \rceil = 1 + 1 = 2$ marks.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Data structures


Solutions:
import sys
input = sys.stdin.readline

def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy, string, math, time, functools, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, chain, combinations, groupby
from operator import itemgetter
from types import GeneratorType
from typing import Iterable, TypeVar, Union
for _ in range(II()):
	(n, m, k) = LI()
	c = LI()
	t = LI()
	d = defaultdict(list)
	for i in range(n):
		d[c[i]].append(t[i])
	arr = []
	for l in d.values():
		l.sort()
		arr.append(l[0])
		s = len(l)
		for i in range(1, s, 2):
			if i + 1 < s:
				arr.append(l[i] + l[i + 1])
	arr.sort()
	s = 0
	ans = 0
	for i in range(len(arr)):
		if s + arr[i] <= k:
			s += arr[i]
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = list(map(int, input().split()))
	t = list(map(int, input().split()))
	d = dict()
	l = dict()
	for i in c:
		d[i] = []
		l[i] = 0
	for i in range(n):
		d[c[i]].append(t[i])
		l[c[i]] += 1
	lis = []
	le = []
	for i in d:
		d[i].sort()
		lis.append(d[i])
		le.append(l[i])
	s = len(le)
	final = []
	for i in range(s):
		final.append(lis[i][0])
		for j in range(1, le[i] - 1, 2):
			final.append(lis[i][j] + lis[i][j + 1])
	final.sort()
	ans = 0
	for i in final:
		if i <= k:
			ans += 1
			k -= i
	print(ans)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = list(map(int, input().split()))
	t = list(map(int, input().split()))
	l = [[0] for i in range(m)]
	l1 = []
	for i in range(n):
		l[c[i] - 1].append(t[i])
	for i in range(len(l)):
		l[i].sort()
		for j in range(0, len(l[i]), 2):
			try:
				l1.append(l[i][j] + l[i][j + 1])
			except:
				pass
	l1.sort()
	s = k
	count = 0
	for i in l1:
		if s < i:
			break
		count += 1
		s -= i
	print(count)


import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key as ctk
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 10 ** 9 + 7
sys.setrecursionlimit(2 * 10 ** 5 + 1)

def comparator(x, y):
	if x[0] == y[0]:
		return x[1] - y[1]
	return True

def ncr(n, r):
	if n < r:
		return 0
	return fc[n] * pow(fc[r] * fc[n - r] % mod, mod - 2, mod) % mod
T = int(input())
for _ in range(T):
	(n, m, k) = map(int, input().split())
	job = list(map(int, input().split()))
	time = list(map(int, input().split()))
	d = dd(list)
	for i in range(n):
		d[job[i]].append(time[i])
	hp = []
	for i in d:
		st = sorted(d[i])
		ll = deque(st)
		top = ll.popleft()
		heapq.heappush(hp, [top, ll, i])
	ss = set()
	ans = dd(int)
	while len(hp):
		ll = heapq.heappop(hp)
		(time, lis, jid) = (ll[0], ll[1], ll[2])
		if jid in ss:
			if time > 10 ** 9:
				actual = time - 10 ** 9
				if actual <= k:
					ans[jid] += 1
					k -= actual
				else:
					break
			elif time <= k:
				ans[jid] += 2
				k -= time
				try:
					x = lis.popleft()
				except:
					x = None
				try:
					y = lis.popleft()
				except:
					y = None
				if x:
					if y:
						heapq.heappush(hp, [x + y, lis, jid])
					else:
						heapq.heappush(hp, [x + 10 ** 9, lis, jid])
			else:
				break
		elif time <= k:
			ans[jid] += 1
			k -= time
			ss.add(jid)
			try:
				x = lis.popleft()
			except:
				x = None
			try:
				y = lis.popleft()
			except:
				y = None
			if x:
				if y:
					heapq.heappush(hp, [x + y, lis, jid])
				else:
					heapq.heappush(hp, [x + 10 ** 9, lis, jid])
		else:
			break
	res = 0
	for i in ans:
		res += (ans[i] + 1) // 2
	print(res)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = [int(i) for i in input().split()]
	t = [int(i) for i in input().split()]
	dict1 = dict()
	for i in c:
		dict1[i] = []
	for i in range(n):
		dict1[c[i]].append(t[i])
	for i in dict1:
		dict1[i].sort()
	list1 = []
	for i in dict1:
		list1.append(dict1[i][0])
		for j in range(1, len(dict1[i]) - 1, 2):
			list1.append(dict1[i][j] + dict1[i][j + 1])
	sum = 0
	list1.sort()
	for i in range(len(list1)):
		if list1[i] <= k:
			sum += 1
			k -= list1[i]
	print(sum)


import heapq as hq
for _ in range(int(input())):
	cnt = 0
	(n, m, k) = map(int, input().split())
	c = list(map(int, input().split()))
	t = list(map(int, input().split()))
	l = [[] for _ in range(m + 1)]
	for i in range(n):
		l[c[i]].append([t[i], c[i]])
	temp = []
	hq.heapify(temp)
	for i in range(1, m + 1):
		if len(l[i]) != 0:
			hq.heapify(l[i])
			hq.heappush(temp, hq.heappop(l[i]))
	while k > 0 and len(temp) != 0:
		t = hq.heappop(temp)
		if k >= t[0]:
			cnt = cnt + 1
			k = k - t[0]
			if len(l[t[1]]) > 1:
				a = hq.heappop(l[t[1]])
				b = hq.heappop(l[t[1]])
				hq.heappush(temp, [a[0] + b[0], b[1]])
		else:
			break
	print(cnt)


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')
from heapq import heapify, heappush, heappop
from collections import defaultdict

def solve():
	(n, m, k) = maps()
	a = [*maps()]
	b = [*maps()]
	(d, e) = (defaultdict(list), [])
	for i in range(n):
		d[a[i]].append(b[i])
	for i in d:
		if len(d[i]) == 1:
			e.append(d[i][0])
			continue
		d[i].sort()
		t = [d[i][0]]
		if len(d[i]) % 2:
			for j in range(1, len(d[i]), 2):
				t.append(d[i][j] + d[i][j + 1])
		else:
			for j in range(1, len(d[i]), 2):
				if j + 1 < len(d[i]):
					t.append(d[i][j] + d[i][j + 1])
		e.extend(t)
	e.sort()
	(tot, num) = (0, 0)
	for i in e:
		num += 1
		tot += i
		if tot > k:
			num -= 1
			break
	print(num)
(t,) = maps()
while t:
	t -= 1
	solve()


import math
for t in range(int(input())):
	(n, m, k) = map(int, input().split())
	sub = list(map(int, input().split()))
	time = list(map(int, input().split()))
	d = dict()
	for s in range(1, m + 1):
		d[s] = []
	for i in range(len(sub)):
		d[sub[i]] += [time[i]]
	for i in range(1, m + 1):
		d[i].sort()
	times = []
	for i in range(1, m + 1):
		ar = d[i]
		if len(ar) == 0:
			continue
		times += [ar[0]]
		for j in range(1, len(ar) - 1, 2):
			times += [ar[j] + ar[j + 1]]
	times.sort()
	sc = 0
	tot = 0
	for tt in range(len(times)):
		if tot + times[tt] <= k:
			tot += times[tt]
			sc += 1
	print(sc)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = list(map(int, input().split()))
	t = list(map(int, input().split()))
	L = dict()
	l = dict()
	for i in c:
		L[i] = []
		l[i] = 0
	for i in range(n):
		L[c[i]].append(t[i])
		l[c[i]] += 1
	L1 = []
	l1 = []
	for i in L:
		L[i].sort()
		L1.append(L[i])
		l1.append(l[i])
	final = []
	for i in range(len(l1)):
		final.append(L1[i][0])
		for j in range(1, len(L1[i]) - 1, 2):
			final.append(L1[i][j] + L1[i][j + 1])
	final.sort()
	ans = 0
	for i in final:
		if i <= k:
			ans += 1
			k -= i
	print(ans)


from collections import defaultdict

def TaskTimes():
	T = int(input())
	for _ in range(T):
		(num_topics, num_subjects, budget) = [int(x) for x in input().split()]
		subjects = [int(x) for x in input().split()]
		costs = [int(x) for x in input().split()]
		costs_to_study_subject = defaultdict(list)
		for (subject, cost) in zip(subjects, costs):
			costs_to_study_subject[subject] += [cost]
		cost_to_get_a_point = []
		for subject in costs_to_study_subject:
			cost_arr = sorted(costs_to_study_subject[subject])
			cost_to_get_a_point += [cost_arr[0]]
			if not len(cost_arr) & 1:
				cost_arr.pop()
			for i in range(1, len(cost_arr), 2):
				cost_to_get_a_point += [sum(cost_arr[i:i + 2])]
		cost_to_get_a_point.sort()
		ans = 0
		i = 0
		while budget > 0 and i < len(cost_to_get_a_point):
			budget -= cost_to_get_a_point[i]
			ans += 1
			i += 1
		if budget < 0:
			ans -= 1
		print(ans)
	return
TaskTimes()


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = list(map(int, input().split()))
	q = list(map(int, input().split()))
	arr = [[] for i in range(m + 1)]
	for i in range(n):
		arr[c[i]].append(q[i])
	v = []
	for i in range(1, m + 1):
		arr[i] = sorted(arr[i])
		if len(arr[i]) > 0:
			v.append(arr[i][0])
		for j in range(1, len(arr[i]), 2):
			if j + 1 != len(arr[i]):
				v.append(arr[i][j] + arr[i][j + 1])
	ans = 0
	v = sorted(v)
	for i in range(len(v)):
		if k >= v[i]:
			k -= v[i]
			ans += 1
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = [[] for i in range(m)]
	for i in range(n):
		l[a[i] - 1].append(b[i])
	for i in range(m):
		l[i].sort()
	new = []
	for i in range(m):
		c = 0
		for j in l[i]:
			c += 1
			if c == 1:
				new.append((j, i))
			elif c % 2 == 1:
				new.append((j + x, i))
			else:
				x = j
	new.sort()
	d = defaultdict(lambda : 0)
	for i in range(len(new)):
		if k < new[i][0]:
			break
		else:
			d[i] += 1
			k -= new[i][0]
	print(sum(d.values()))


from collections import *
for u in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = [[0] for i in range(m)]
	for i in range(n):
		d[a[i] - 1].append(b[i])
	l = []
	for i in range(m):
		d[i].sort()
		for j in range(0, len(d[i]) - 1, 2):
			l.append(d[i][j] + d[i][j + 1])
	l.sort()
	c = 0
	for i in range(len(l)):
		if l[i] <= k:
			k -= l[i]
			c += 1
		else:
			break
	print(c)


t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	k = list(map(int, input().split()))
	l = list(map(int, input().split()))
	s1 = [[0] for i in range(b)]
	for i in range(a):
		s1[k[i] - 1].append(l[i])
	s2 = []
	for i in range(b):
		s1[i].sort()
		for j in range(len(s1[i]) // 2):
			s2.append(s1[i][2 * j] + s1[i][2 * j + 1])
	s2.sort()
	i = 0
	j = 0
	while i < len(s2) and j + s2[i] <= c:
		j += s2[i]
		i += 1
	print(i)


for _ in range(int(input())):
	(N, M, K) = map(int, input().split())
	C = list(map(int, input().split()))
	T = [(int(j), i) for (i, j) in enumerate(input().split())]
	T.sort()
	F = [[] for i in range(M)]
	Q = []
	for (t, i) in T:
		s = C[i] - 1
		if len(F[s]) & 1 == 0:
			c = t + (F[s][-1] if len(F[s]) != 0 else 0)
			Q.append(c)
		F[s].append(t)
	Q.sort()
	ans = 0
	i = 0
	while i < len(Q) and Q[i] <= K:
		K -= Q[i]
		ans += 1
		i += 1
	print(ans)


from bisect import *
from collections import *
from sys import stdin, stdout
from queue import *
from itertools import *
from heapq import *
from random import *
from statistics import *
from math import *
from re import *
import array
import operator
from copy import *
lines = stdin.readlines()
out = stdout.write
lines.reverse()

def input():
	return lines.pop().strip('\n')

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

def readStrList():
	return list(map(str, input().split()))
for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = readIntList()
	t = readIntList()
	arr = []
	mp = defaultdict(int)
	wp = defaultdict(int)
	for i in range(n):
		arr.append((t[i], c[i]))
	arr.sort()
	brr = []
	for i in range(n):
		if mp[arr[i][1]] % 2 != 0:
			wp[arr[i][1]] = arr[i][0]
		else:
			brr.append((arr[i][0] + wp[arr[i][1]], arr[i][1]))
		mp[arr[i][1]] += 1
	brr.sort()
	d = defaultdict(list)
	ans = 0
	left = k
	for i in range(len(brr)):
		if left < brr[i][0]:
			break
		ans += 1
		left -= brr[i][0]
	print(ans)


for t in range(int(input())):
	(N, M, K) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = [[a[i], b[i]] for i in range(N)]
	arr.sort()
	vis = [0] * (N + 1)
	narr = []
	i = 0
	while i < N:
		if vis[arr[i][0]]:
			if i < N - 1 and arr[i + 1][0] == arr[i][0]:
				narr.append([arr[i][1] + arr[i + 1][1], arr[i][0]])
				i += 2
			else:
				i += 1
		else:
			narr.append([arr[i][1], arr[i][0]])
			vis[arr[i][0]] = 1
			i += 1
	narr.sort()
	count = [0] * (N + 1)
	for (i, j) in narr:
		if i <= K:
			K -= i
			if count[j]:
				count[j] += 2
			else:
				count[j] += 1
		else:
			break
	ans = 0
	for i in count:
		ans += (i + 1) // 2
	print(ans)


from collections import Counter
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = {}
	for i in range(n):
		c[a[i]] = []
	for i in range(n):
		c[a[i]].append(b[i])
	e = []
	for i in c:
		if len(c[i]) > 1:
			c[i].sort()
			if len(c[i]) % 2 == 0:
				d = [c[i][0]]
				for j in range(1, len(c[i]), 2):
					if j == len(c[i]) - 1:
						break
					d.append(c[i][j] + c[i][j + 1])
			else:
				d = [c[i][0]]
				for j in range(1, len(c[i]), 2):
					d.append(c[i][j] + c[i][j + 1])
			e.extend(d)
		else:
			e.extend(c[i])
	e.sort()
	k1 = 0
	c1 = 0
	for i in e:
		c1 += 1
		k1 += i
		if k1 > k:
			c1 -= 1
			break
	print(c1)


for tcase in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = list(map(int, input().split()))
	t = list(map(int, input().split()))
	s1 = [[0] for i in range(m)]
	for i in range(n):
		s1[c[i] - 1].append(t[i])
	s2 = []
	for i in range(m):
		s1[i].sort()
		for j in range(len(s1[i]) // 2):
			s2.append(s1[i][2 * j] + s1[i][2 * j + 1])
	s2.sort()
	(i, time) = (0, 0)
	while i < len(s2) and time + s2[i] <= k:
		time += s2[i]
		i += 1
	print(i)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(n, m, k) = ma()
	c = lis()
	tt = lis()
	ind = {}
	for i in range(n):
		try:
			ind[c[i]].append(tt[i])
		except:
			ind[c[i]] = [tt[i]]
	for i in ind.keys():
		ind[i].sort(reverse=True)
	tot = []
	res = 0
	for i in ind.keys():
		x = ind[i].pop()
		tot.append([1, x])
		while len(ind[i]) > 1:
			x = ind[i].pop()
			y = ind[i].pop()
			tot.append([1, x + y])
	tot.sort()
	for i in tot:
		k -= i[1]
		if k < 0:
			break
		res += 1
	print(res)


import heapq, math
from collections import deque
tc = int(input())
for _ in range(tc):
	(n, m, k) = list(map(int, input().split()))
	subject = list(map(int, input().split()))
	hours = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([hours[i], subject[i], 1])
	heapq.heapify(l)
	taken = [0 for _ in range(m + 1)]
	totake = [[] for _ in range(m + 1)]
	while k > 0 and len(l) > 0:
		(hour, subj, count) = heapq.heappop(l)
		totcount = taken[subj] + count
		if totcount % 2 == 1:
			if hour <= k:
				taken[subj] = totcount
				k -= hour
		elif len(totake[subj]) == 0:
			totake[subj].append(hour)
		else:
			c1 = totake[subj].pop()
			totalhour = c1 + hour
			heapq.heappush(l, [totalhour, subj, 2])
	ans = 0
	for i in taken:
		ans += math.ceil(i / 2)
	print(ans)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = list(map(int, input().split()))
	t = list(map(int, input().split()))
	l = [[] for _ in range(m)]
	for i in range(n):
		l[c[i] - 1].append(t[i])
	new = []
	for i in range(m):
		if not l[i]:
			continue
		l[i].sort()
		nl = [l[i][0]]
		try:
			for j in range(1, len(l[i]), 2):
				nl.append(l[i][j] + l[i][j + 1])
		except:
			pass
		new += nl
	new.sort()
	c = 0
	for i in new:
		if k - i >= 0:
			k -= i
		else:
			break
		c += 1
	print(c)


from heapq import heapify, heappop, heappush
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = list(map(int, input().split()))
	t = list(map(int, input().split()))
	z = [[] for _ in range(m)]
	for i in range(n):
		heappush(z[c[i] - 1], t[i])
	l = []
	for i in range(m):
		if z[i]:
			heappush(l, (heappop(z[i]), i))
	ans = 0
	while k and l:
		(time, g) = heappop(l)
		if k - time >= 0:
			k -= time
			ans += 1
			if len(z[g]) >= 2:
				heappush(l, (heappop(z[g]) + heappop(z[g]), g))
	print(ans)


def main():
	(n, m, k) = map(int, input().split())
	subjects = list(map(int, input().split()))
	times = list(map(int, input().split()))
	dic = {}
	for i in range(n):
		(s, t) = (subjects[i], times[i])
		if s in dic:
			dic[s].append(t)
		else:
			dic[s] = [t]
	for s in dic:
		dic[s].sort()
	anotherDic = {}
	for s in dic:
		anotherDic[s] = [dic[s][0]]
		arr = dic[s]
		for i in range(2, len(arr), 2):
			anotherDic[s].append(arr[i] + arr[i - 1])
	arr = []
	for s in anotherDic:
		arr.extend(anotherDic[s])
	arr.sort()
	ans = 0
	count = 0
	for num in arr:
		if ans + num <= k:
			count += 1
			ans += num
		else:
			break
	print(count)
t = int(input())
for _ in range(t):
	main()