Did you know you can download more RAM? There is a shop with $n$ different pieces of software that increase your RAM. The $i$-th RAM increasing software takes $a_i$ GB of memory to run (temporarily, once the program is done running, you get the RAM back), and gives you an additional $b_i$ GB of RAM (permanently). Each software can only be used once. Your PC currently has $k$ GB of RAM.

Note that you can't use a RAM-increasing software if it takes more GB of RAM to use than what you currently have.

Since RAM is the most important thing in the world, you wonder, what is the maximum possible amount of RAM achievable?


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integers $n$ and $k$ ($1 \le n \le 100$, $1 \le k \le 1000$). Then two lines follow, each containing $n$ integers describing the arrays $a$ and $b$ ($1 \le a_i, b_i \le 1000$).


-----Output-----

For each test case, output a single line containing the largest amount of RAM you can achieve.


-----Examples-----

Input
4
3 10
20 30 10
9 100 10
5 1
1 1 5 1 1
1 1 1 1 1
5 1
2 2 2 2 2
100 100 100 100 100
5 8
128 64 32 16 8
128 64 32 16 8
Output
29
6
1
256


-----Note-----

In the first test case, you only have enough RAM to run the third software initially, but that increases your RAM to $20$ GB, which allows you to use the first software, increasing your RAM to $29$ GB. The only software left needs $30$ GB of RAM, so you have to stop here.

In the second test case, you can use the first, second, fourth and fifth software that need only $1$ GB of RAM per software to run to increase your RAM to $5$ GB, and then use the last remaining one to increase your RAM to $6$ GB.

In the third test case, all the software need more than $1$ GB of RAM to run, so the amount of RAM you have stays at $1$ GB.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Sorting

Greedy algorithms


Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mem = list(map(int, input().split()))
	ram = list(map(int, input().split()))
	dp = []
	for i in range(n):
		dp.append([mem[i], ram[i]])
	dp.sort()
	rm = k
	for i in dp:
		if i[0] <= rm:
			rm += i[1]
		else:
			break
	print(rm)


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	d = {}
	for i in range(n):
		if a[i] in d:
			d[a[i]] += b[i]
		else:
			d[a[i]] = b[i]
	key = sorted(list(d.keys()))
	for i in key:
		if k >= i:
			k += d[i]
		else:
			break
	print(k)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(get_ints())

def input():
	return sys.stdin.readline().strip()
T = int(input())
while T > 0:
	(n, k) = get_ints()
	Arr1 = get_array()
	Arr2 = get_array()
	curr = k
	p = []
	for i in range(n):
		p.append((Arr1[i], Arr2[i]))
	p.sort(key=lambda x: (x[0], -x[1]))
	i = 0
	ans = k
	while i < n and curr >= p[i][0]:
		curr += p[i][1]
		ans = max(ans, curr)
		i += 1
	print(ans)
	T -= 1


import sys
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
t = int(input())
for _ in [0] * t:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for (i, j) in zip(a, b):
		l += [(i, j)]
	l.sort()
	for (i, j) in l:
		if k >= i:
			k += j
	print(k)


def solve(k, a, b):
	n = len(a)
	s = [[a[i], b[i]] for i in range(n)]
	s = sorted(s, key=lambda x: x[0])
	cur = k
	for i in range(n):
		if s[i][0] > cur:
			return cur
		cur += s[i][1]
	return cur
t = int(input())
out = []
for case in range(t):
	s = list(map(int, input().split(' ')))
	(n, k) = (s[0], s[1])
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	out.append(str(solve(k, a, b)))
print('\n'.join(out))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = map(int, input().split())
	b = map(int, input().split())
	arr = sorted(zip(a, b), key=lambda x: x[0])
	sm = k
	for (a, b) in arr:
		if a <= sm:
			sm += b
		else:
			break
	print(sm)


t = int(input())
while t:
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(0, n):
		l.append([a[i], b[i]])
	y = sorted(l, key=lambda x: x[0])
	for i in y:
		if i[0] <= k:
			k += i[1]
	print(k)
	t -= 1


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	result = list(zip(a, b))
	result.sort(key=lambda x: x[0])
	ans = k
	for i in result:
		if i[0] > ans:
			return ans
		ans += i[1]
	return ans

def main():
	t = int(input())
	while t:
		print(solve())
		t -= 1
main()


T = int(input())
while T:
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	listOflists = list(zip(a, b))
	listOflists.sort(key=lambda x: x[0])
	for i in listOflists:
		if i[0] <= k:
			k += i[1]
	print(k)
	T -= 1


testcases = int(input())
out = []
for _ in range(testcases):
	(shop, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	new = list(zip(a, b))
	new.sort(key=lambda x: x[0])
	for (x, y) in new:
		if k >= x:
			k += y
	out.append(k)
for o in out:
	print(o)


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = []
	for i in range(n):
		x.append([a[i], b[i]])
	x.sort()
	for i in range(n):
		if x[i][0] <= k:
			k += x[i][1]
		else:
			break
	print(k)
	t -= 1


import math

def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append([a[i], b[i]])
	arr.sort()
	s = k
	for i in range(len(arr)):
		if arr[i][0] <= s:
			s += arr[i][1]
		else:
			break
	print(s)
t = int(input())
for i in range(t):
	solve()


T = int(input())
for t in range(T):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	f = sorted(list(zip(a, b)))
	for i in f:
		if i[0] <= k:
			k += i[1]
		else:
			break
	print(k)


class a:

	def __init__(self, x):
		self.x = x
		self.y = 0

def keys(a):
	return a.x
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	b = [a(i) for i in list(map(int, input().split()))]
	c = list(map(int, input().split()))
	for i in range(n):
		b[i].y = c[i]
	b.sort(key=keys)
	for i in range(n):
		if k >= b[i].x:
			k += b[i].y
		else:
			break
	print(k)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	q = list(zip(a, b))
	q.sort()
	for i in range(n):
		if q[i][0] <= k:
			k += q[i][1]
		else:
			break
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = [[i, j] for (i, j) in zip(a, b)]

	def myfun(s):
		return s[0]
	c.sort(key=myfun)
	ram = k
	for i in range(n):
		if c[i][0] > ram:
			break
		else:
			ram += c[i][1]
	print(ram)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = [0] * n
	for i in range(n):
		arr[i] = list((a[i], b[i]))
	arr.sort(key=lambda x: x[0])
	for i in arr:
		if i[0] <= k:
			k += i[1]
	print(k)


t = int(input())
for tt in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = []
	for i in range(len(a)):
		d.append((a[i], b[i]))
	d.sort(key=lambda x: x[0])
	for ram in d:
		if k >= ram[0]:
			k += ram[1]
		else:
			break
	print(k)


import math
t = int(input())
while t:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = list(zip(a, b))
	x.sort(key=lambda y: (y[0], -y[1]))
	for i in range(0, n):
		if x[i][0] <= k:
			k = k + x[i][1]
		else:
			break
	print(k)
	t = t - 1


R = lambda : map(int, input().split())
(t,) = R()
exec(t * 'n,k=R()\nfor x,y in sorted(zip(R(),R())):k+=(x<=k)*y\nprint(k)\n')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append([arr1[i], arr2[i]])
	arr.sort()
	i = 0
	while i < n and k >= arr[i][0]:
		if k >= arr[i][0]:
			k += arr[i][1]
		else:
			break
		i += 1
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(a, b) = [[*map(int, input().split())] for i in range(2)]
	for (i, j) in sorted(zip(a, b)):
		if k - i < 0:
			break
		k += j
	print(k)


import sys
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

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

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

def solve(a, b, k):
	zipped = list(reversed(sorted(zip(a, b))))
	available = k
	while True:
		(prog, additional) = zipped.pop()
		if prog <= available:
			available += additional
		else:
			return available
		if not zipped:
			return available
for _ in range(inp()):
	(n, k) = read_int_list()
	a = read_int_list()
	b = read_int_list()
	print(solve(a, b, k))


def find_max_ram(n, k, a, b):
	ramsoft = list(zip(a, b))
	ramsoft.sort(key=lambda x: x[0])
	for (cost, value) in ramsoft:
		if cost <= k:
			k += value
		else:
			return k
	return k
T = int(input())
for t in range(T):
	(n, k) = [int(j) for j in input().split()]
	a = [int(j) for j in input().split()]
	b = [int(j) for j in input().split()]
	print(find_max_ram(n, k, a, b))


for u in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(w) for w in input().split()]
	b = [int(w) for w in input().split()]
	x = [[a[i], b[i]] for i in range(n)]
	x = sorted(x)
	for i in range(n):
		if k >= x[i][0]:
			k += x[i][1]
		else:
			break
	print(k)


tst = int(input())
for i in range(tst):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = zip(a, b)
	for i in sorted(c):
		if i[0] <= k:
			k += i[1]
	print(k)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	req = list(map(int, input().split()))
	ram = list(map(int, input().split()))
	for (p, q) in sorted(zip(req, ram)):
		if p <= k:
			k += q
		else:
			break
	print(k)


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	for i in range(n):
		c.append([a[i], b[i]])
	c.sort()
	for i in range(n):
		if k >= c[i][0]:
			k += c[i][1]
	print(k)
t = int(input())
while t:
	solve()
	t -= 1


for z in range(int(input())):
	(n, k) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	lis = sorted(zip(a, b))
	for i in range(n):
		if lis[i][0] <= k:
			k += lis[i][1]
		else:
			break
	print(k)


import sys
iterNum = int(input())
(NK, A, B) = ([], [], [])
for _ in range(iterNum):
	NK.append(sys.stdin.readline().rstrip('\n'))
	A.append(sys.stdin.readline().rstrip('\n'))
	B.append(sys.stdin.readline().rstrip('\n'))
N = [int(i.split(' ')[0]) for i in NK]
K = [int(i.split(' ')[1]) for i in NK]
for (a, b, n, k) in zip(A, B, N, K):
	a = [int(i) for i in a.split(' ')]
	b = [int(i) for i in b.split(' ')]
	abList = [[i, j] for (i, j) in zip(a, b)]
	abList.sort()
	for ab in abList:
		if ab[0] <= k:
			k += ab[1]
		else:
			break
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b = [x for (_, x) in sorted(zip(a, b))]
	a.sort()
	for i in range(len(a)):
		if a[i] <= k:
			k += b[i]
		else:
			break
	print(k)


import sys
from operator import itemgetter
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
number_tests = inp()
for _ in range(number_tests):
	numbers = inlt()
	answer = numbers[1]
	first_list = inlt()
	second_list = inlt()
	combined_list = list(zip(first_list, second_list))
	combined_list.sort(key=itemgetter(0))
	for number in combined_list:
		if answer >= number[0]:
			answer += number[1]
	print(answer)


rii = lambda : [int(x) for x in input().split()]
t = int(input())
for _ in range(t):
	(n, k) = rii()
	software = sorted(list(zip(rii(), rii())), key=lambda x: (x[0], -x[1]))
	for (needed, recieved) in software:
		if k < needed:
			break
		k += recieved
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = sorted(zip(a, b))
	a = [x for (x, y) in c]
	b = [y for (x, y) in c]
	for x in range(n):
		if a[x] <= k:
			k += b[x]
		else:
			break
	print(k)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	zipped_pairs = zip(a, b)
	a = sorted(a)
	c = [x for (_, x) in sorted(zipped_pairs)]
	for i in range(n):
		if a[i] <= k:
			k += c[i]
	print(k)


def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = list(zip(a, b))
	l.sort()
	for i in range(n):
		if l[i][0] <= k:
			k += l[i][1]
		else:
			break
	return k
for _ in range(int(input())):
	print(main())


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	aa = [int(a) for a in input().split()]
	bb = [int(b) for b in input().split()]
	ab = sorted(zip(aa, bb))
	for (a, b) in ab:
		if a > k:
			break
		k += b
	print(k)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = [[float('inf'), float('inf')]]
	for i in range(n):
		s.append([a[i], b[i]])
	s.sort()
	ans = 0
	while k >= s[0][0]:
		k = k + s[0][1]
		s.pop(0)
	print(k)
	t = t - 1


t = int(input())
for i in range(t):
	nk = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	z = []
	for i in range(len(a)):
		z.append([a[i], b[i]])
	sz = sorted(z)
	k = nk[1]
	for i in range(len(sz)):
		if sz[i][0] <= k:
			k += sz[i][1]
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = [[a[i], b[i]] for i in range(n)]
	c.sort()
	for (x, y) in c:
		if x > k:
			break
		k += y
	print(k)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	ram_software = zip(a, b)
	ram_software = sorted(ram_software)
	for i in range(n):
		if k >= ram_software[i][0]:
			k += ram_software[i][1]
		else:
			break
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a1 = map(int, input().split())
	b2 = map(int, input().split())
	y = list(zip(a1, b2))
	y.sort()
	s = 0
	for j in range(n):
		if y[j][0] <= k + s:
			s += y[j][1]
	print(k + s)


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)

def solve() -> str:
	(_, k) = map(int, input().split())
	for (a, b) in sorted(zip(list(map(int, input().split())), list(map(int, input().split())))):
		if a > k:
			break
		k += b
	print(k)

def main() -> None:
	t = int(input())
	for _ in range(t):
		solve()
main()


def find_greedy_sol(ram, software):
	software = sorted(software)
	for (i, j) in software:
		if i <= ram:
			ram += j
		else:
			break
	print(ram)
nb = int(input())
for k in range(nb):
	(ln, ram) = [int(i) for i in input().split()]
	ram_necessary = [int(i) for i in input().split()]
	ram_unlock = [int(i) for i in input().split()]
	software = [(ram_necessary[i], ram_unlock[i]) for i in range(ln)]
	find_greedy_sol(ram, software)


testCases = int(input())
for _ in range(testCases):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for (i, j) in sorted(enumerate(a), key=lambda x: x[1]):
		if j <= k:
			k += b[i]
		else:
			break
	print(k)


import sys
input = sys.stdin.readline

def solve(n, k, a, b):
	arr = list(zip(a, b))
	arr.sort(key=lambda x: (x[0], -x[1]))
	i = 0
	curr = k
	while i < n and arr[i][0] <= curr:
		curr += arr[i][1]
		i += 1
	return curr
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(solve(n, k, a, b))


from sys import stdin

def rei():
	return list(map(int, stdin.readline().strip().split(' ')))

def res():
	return stdin.readline().rstrip()

def prno():
	print('NO')

def pryes():
	print('YES')

def solve():
	(n, k) = rei()
	a = rei()
	b = rei()
	ab = sorted(list(zip(a, b)), key=lambda x: x[0])
	for (a, b) in ab:
		if a <= k:
			k += b
		else:
			break
	print(k)
t = rei()[0]
for _ in range(t):
	solve()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(zip(a, b))
	c.sort()
	for (index, val) in enumerate(c):
		if k >= val[0]:
			k += val[1]
		else:
			break
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()[:n]))
	b = list(map(int, input().split()[:n]))
	y = [i[0] for i in sorted(enumerate(a), key=lambda x: x[1])]
	a.sort()
	l = []
	for i in range(len(a)):
		if k >= a[i]:
			k += b[y[i]]
		if i == len(a) - 1:
			l.append(k)
	print(*l)


alpha = []
beta = []
gamma = []
t = int(input())
for i in range(t):
	n = [int(s) for s in input().split(' ')]
	a = [int(s) for s in input().split(' ')]
	b = [int(s) for s in input().split(' ')]
	alpha.append(n)
	beta.append(a)
	gamma.append(b)
for i in range(t):
	(n, k) = alpha[i]
	a = beta[i]
	b = gamma[i]
	z = []
	for j in range(len(a)):
		z.append([a[j], b[j]])
	z.sort()
	for j in range(len(a)):
		if z[j][0] <= k:
			k += z[j][1]
		else:
			break
	print(k)


n = int(input())
for i in range(n):
	(ram_size, current_ram) = list(map(int, input().split(' ')))
	ram_consumption = list(map(int, input().split(' ')))
	ram_value = list(map(int, input().split(' ')))
	d = {}
	total_ram = current_ram
	for j in range(ram_size):
		d[j] = [ram_consumption[j], ram_value[j]]
	d = dict(sorted(d.items(), key=lambda x: x[1][0]))
	for (key, value) in d.items():
		if value[0] <= total_ram:
			total_ram += value[1]
		else:
			break
	print(total_ram)


import heapq
T = int(input())
for _ in range(T):
	inLine = input().split(' ')
	(N, currentRam) = (int(inLine[0]), int(inLine[1]))
	ramRequired = input().split(' ')
	ramToGain = input().split(' ')
	ramTuples = [0] * N
	for i in range(N):
		ramTuples[i] = (int(ramRequired[i]), int(ramToGain[i]))
	heapq.heapify(ramTuples)
	while len(ramTuples) > 0 and ramTuples[0][0] <= currentRam:
		currentRam += heapq.heappop(ramTuples)[1]
	print(currentRam)


while True:
	try:
		test_cases = int(input())
		for i in range(test_cases):
			data = [int(x) for x in input().rstrip('\n').split()]
			n = data[0]
			k = data[1]
			A = [int(x) for x in input().rstrip('\n').split()]
			B = [int(x) for x in input().rstrip('\n').split()]
			A_B = []
			a_to_b = {}
			for i in range(len(A)):
				A_B.append((A[i], B[i]))
			A_B.sort()
			for i in range(len(A_B)):
				if k >= A_B[i][0]:
					k += A_B[i][1]
			print(k)
	except EOFError:
		break


numTests = int(input())
for num in range(numTests):
	adders = dict()
	line = input().split(' ')
	options = int(line[0])
	ram = int(line[1])
	ramNeeded = input().split(' ')
	ramAdded = input().split(' ')
	for i in range(options):
		if int(ramNeeded[i]) in adders:
			adders[int(ramNeeded[i])] += int(ramAdded[i])
		else:
			adders[int(ramNeeded[i])] = int(ramAdded[i])
	ramNeededList = sorted(adders.keys())
	for i in range(len(ramNeededList)):
		if ram >= ramNeededList[i]:
			ram += adders[int(ramNeededList[i])]
		else:
			break
	print(ram)


def main():
	numCases = int(input(''))
	for i in range(numCases):
		line1 = input('').split()
		n = int(line1[0])
		k = int(line1[1])
		line2 = [int(x) for x in input('').split()]
		line3 = [int(x) for x in input('').split()]
		pairs = [(line2[i], line3[i]) for i in range(len(line2))]
		pairs.sort()
		for ele in pairs:
			if k >= ele[0]:
				k += ele[1]
		print(k)
main()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a1 = []
	for i in range(n):
		a1.append((a[i], i))
	a1.sort()
	for i in range(n):
		if a1[i][0] <= k:
			k += b[a1[i][1]]
	print(k)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mk = []
	for i in range(n):
		mk.append([a[i], b[i]])
	mk.sort()
	for i in range(n):
		if k >= mk[i][0]:
			k = k + mk[i][1]
		else:
			break
	print(k)
	t = t - 1


t = int(input())
for _ in range(t):
	(n, ram) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sortedA = sorted(a)
	if sortedA[0] > ram:
		print(ram)
		continue
	for e in sortedA:
		if e <= ram:
			ram += b[a.index(e)]
			a[a.index(e)] = 's'
		else:
			continue
	print(ram)


def main():
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		w = []
		for j in range(n):
			w.append([a[j], b[j]])
		w = sorted(w)
		for j in range(n):
			if w[j][0] <= k:
				k += w[j][1]
		print(k)
main()


t = int(input())
for _ in range(t):
	inp = input().split()
	n = int(inp[0])
	k = int(inp[1])
	lsa = input().split()
	lsb = input().split()
	lst = []
	for i in range(n):
		lst.append((int(lsa[i]), int(lsb[i])))
	lst.sort(key=lambda x: x[0])
	for i in lst:
		if k >= i[0]:
			k += i[1]
		else:
			break
	print(k)


for _ in range(int(input())):
	d = input().split(' ')
	n = int(d[0])
	ozu = int(d[1])
	lst1 = list(map(int, input().split(' ')))
	lst2 = list(map(int, input().split(' ')))
	for (x, y) in sorted(zip(lst1, lst2)):
		if x > ozu:
			break
		ozu += y
	print(ozu)


from math import ceil, log10
import bisect
import math
from collections import defaultdict
from itertools import groupby
from collections import defaultdict, Counter
from heapq import heappop, heappush
from collections import deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(zip(a, b))
	c.sort(key=lambda x: x[0])
	for (reqd, inc) in c:
		if k < reqd:
			break
		k += inc
	print(k)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	c = list(zip(x, y))
	c.sort()
	for (i, j) in c:
		if b >= i:
			b += j
	print(b)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a_copy = [i for i in a]
	a_copy.sort()
	while a_copy[0] <= k:
		s = a_copy[0]
		k += b.pop(a.index(s))
		a.remove(s)
		a_copy.pop(0)
		if len(a_copy) == 0:
			break
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	for (a, b) in sorted(zip(map(int, input().split()), input().split())):
		if a > k:
			break
		k += int(b)
	print(k)


def moreRAM(l, a, b, k):
	arr = [(0, 0)]
	for i in range(l):
		arr.append((a[i], b[i]))
	arr.sort(key=lambda x: x[0])
	for i in range(len(arr)):
		if arr[i][0] <= k:
			k = k + arr[i][1]
	return k
T = int(input())
for i in range(T):
	arr = list(map(int, input().split()))
	l = arr[0]
	k = arr[1]
	print(moreRAM(l, list(map(int, input().split())), list(map(int, input().split())), k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	v = [[0, 0] for i in range(n)]
	j = 0
	for i in map(int, input().split()):
		v[j][0] = i
		j += 1
	j = 0
	for i in map(int, input().split()):
		v[j][1] = i
		j += 1
	v.sort()
	for i in v:
		if i[0] > k:
			break
		else:
			k += i[1]
	print(k)


t = int(input())
for i in range(t):
	nk = input().split()
	n = int(nk[0])
	k = int(nk[1])
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	tmp = []
	for i in range(n):
		tmp.append((a[i], b[i]))
	tmp.sort()
	for value in tmp:
		if value[0] > k:
			break
		else:
			k += value[1]
	print(k)


t = int(input())
while t != 0:
	t -= 1
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for (i, j) in sorted(zip(a, b)):
		if k - i < 0:
			break
		k += j
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted(list(zip(list(map(int, input().split())), list(map(int, input().split())))), key=lambda x: x[0])
	for i in l:
		if i[0] <= k:
			k += i[-1]
		else:
			break
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = sorted(zip(a, b))
	t = k
	for (i, j) in p:
		if i <= t:
			t += j
	print(t)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	d = list(map(int, input().split()))
	if b < min(c):
		print(b)
	else:
		e = []
		for j in range(a):
			e.append((c[j], d[j]))
		e.sort()
		for k in range(len(e)):
			if e[k][0] <= b:
				b += e[k][1]
		print(b)


t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	ram = int(k)
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mem = []
	for i in range(n):
		ele = []
		ele.append(a[i])
		ele.append(b[i])
		mem.append(ele)
	sm = sorted(mem)
	for i in range(n):
		if sm[i][0] <= ram:
			ram = ram + sm[i][1]
	print(ram)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr1 = list(map(int, input().split()))
	ans = [(arr[i], arr1[i]) for i in range(n)]
	ans.sort()
	for i in ans:
		if i[0] <= k:
			k += i[1]
	print(k)
	t -= 1


for i in range(int(input())):
	(n, k) = [int(i) for i in input().split(' ')]
	a = [int(i) for i in input().split(' ')]
	b = [int(i) for i in input().split(' ')]
	c = [[i, j] for (i, j) in zip(a, b)]
	c.sort(key=lambda x: x[0])
	for i in range(n):
		temp = c[i][0]
		extra = c[i][1]
		if k >= temp:
			k += extra
		else:
			break
	print(k)


t = int(input())
for z in range(t):
	d = {}
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = [x for (_, x) in sorted(zip(a, b))]
	a.sort()
	for i in range(n):
		if a[i] <= k:
			k = k + c[i]
	print(k)


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[i] = a[i]
	res = {key: val for (key, val) in sorted(d.items(), key=lambda ele: ele[1])}
	for i in res:
		if k < res[i]:
			break
		else:
			k += b[i]
	print(k)


mod = 10000000
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ab = list(zip(a, b))
	ab.sort()
	for (a, b) in ab:
		if a <= k:
			k += b
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	assert len(a) == len(b) == n
	for (req, add) in sorted(zip(a, b)):
		if req > k:
			break
		k += add
	print(k)


import collections
t = int(input())
while t:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	has_map = {}
	for i in range(n):
		if a[i] in has_map:
			has_map[a[i]] += b[i]
		else:
			has_map[a[i]] = b[i]
	od = dict(sorted(has_map.items()))
	for (key, value) in od.items():
		if key <= k:
			k += value
	print(k)
	t -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	p = list(map(int, input().split()))
	q = list(map(int, input().split()))
	f = []
	for i in range(a):
		f.append([p[i], q[i]])
	f = sorted(f, key=lambda l: l[0])
	for i in range(a):
		if b >= f[i][0]:
			b += f[i][1]
		else:
			break
	print(b)


T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split(' ')]
	a = [int(x) for x in input().split(' ')]
	b = [int(x) for x in input().split(' ')]
	c = sorted(zip(a, b))
	j = 0
	for (i, j) in c:
		if i <= k:
			k += j
		else:
			break
	print(k)


tests = int(input())
for test in range(tests):
	(n, memory) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	d = list(zip(a, b))
	d.sort(key=lambda x: x[0])
	for x in d:
		if x[0] <= memory:
			memory += x[1]
	print(memory)


for l in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ab = list(zip(a, b))
	ab.sort()
	for (a, b) in ab:
		if a <= k:
			k += b
	print(k)


def sor(val):
	return val[0]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append((a[i], b[i]))
	arr.sort(key=sor)
	i = 0
	while i < n and k >= arr[i][0]:
		k = k + arr[i][1]
		i = i + 1
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mergedList = [[a[i], b[i]] for i in range(n)]
	mergedList.sort(key=lambda x: x[0])
	for x in mergedList:
		if x[0] <= k:
			k += x[1]
	print(k)


t = int(input())
for _ in range(t):
	(n, k) = [int(XX) for XX in input().split()]
	a = [int(XX) for XX in input().split()]
	b = [int(XX) for XX in input().split()]
	allSoftware = list(sorted([(a[i], b[i]) for i in range(n)]))
	for i in range(n):
		if k < allSoftware[i][0]:
			break
		k += allSoftware[i][1]
	print(k)


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	k = inputs[1]
	lista = [int(num) for num in input().split()]
	listb = [int(num) for num in input().split()]
	c1 = 0
	zipped_lists = zip(lista, listb)
	sorted_pairs = sorted(zipped_lists)
	tuples = zip(*sorted_pairs)
	(lista, listb) = [list(tuple) for tuple in tuples]
	ram = k
	i = 0
	for i in range(0, len(lista)):
		if lista[i] <= ram:
			ram += listb[i]
		else:
			break
	print(ram)


size = int(input())
output = ''
for i in range(0, size):
	(nb, initial) = list(map(int, input().split()))
	programs = list(map(int, input().split()))
	rewards = list(map(int, input().split()))
	data = dict()
	for k in range(0, len(programs)):
		try:
			data[programs[k]] += rewards[k]
		except KeyError:
			data[programs[k]] = rewards[k]
	j = 0
	programs = list(dict.fromkeys(programs))
	programs.sort()
	while j < len(programs) and initial >= programs[j]:
		initial += data[programs[j]]
		j += 1
	output += str(initial) + '\n'
print(output)


answers = []
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	new_a = []
	for (index, value) in enumerate(a):
		new_a.append((value, index))
	new_a.sort(key=lambda tup: tup[0])
	for item in new_a:
		(value, index) = (item[0], item[1])
		if value > k:
			break
		k += b[index]
	ans = k
	answers.append(ans)
for i in answers:
	print(i)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = list(zip(A, B))
	C = sorted(C, key=lambda item: item[0])
	for (a, b) in C:
		if k >= a:
			k += b
	print(k)