Read problem statements in [Russian] and [Mandarin Chinese].

Chef goes to a candy store that sells N different candies. For each candy, we know its price and sweetness. Chef has D dollars and can take a maximum of 2 candies, one in each hand. Find the maximum total sweetness he can buy under the given constraints.

NOTE: Since the input-output is large, prefer using fast input-output methods. 

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

- The first line contains an integer T, the number of test cases. Then the test cases follow. 
- Each test case contains three lines of input.
- First line will contain 2 space separated integers N and D, the number of different candies and the amount of money Chef has. 
- Second line contains N space separated integers P_{1}, P_{2}, \ldots, P_{N}, where P_{i} is the price of the i^{th} candy.
- Third line contains N space separated integers S_{1}, S_{2}, \ldots, S_{N}, where S_{i} is the sweetness of the i^{th} candy. 

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

For each testcase, output in a single line, the maximum total sweetness Chef can buy with the money he has, and with at most two candies.

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

$1 ≤ T ≤ 2.5*10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ D ≤ 10^{9}$
$1 ≤ P_{i}, S_{i} ≤ 10^{9}$
- Sum $N$ over all testcases is atmost $10^{6}$.

----- Sample Input 1 ------ 
3
2 10
1 2 
2 1 
5 7
1 2 3 4 5
1 2 3 4 5
5 7
6 6 6 6 6
5 4 3 2 1
----- Sample Output 1 ------ 
3
7
5
----- explanation 1 ------ 
TestCase $1$: Chef can collect both the candies available with the money he has.

TestCase $2$: Chef can collect candies at index $[2, 5]$ or $[3, 4]$. In both cases, he will get the total sweetness of $7$.

TestCase $3$: Since the price of all candies is the same, it's always optimal to choose the candies with maximum sweetness. Also, in this case, no more than one candy can be chosen.

Difficulty: VERY_HARD
Tags: Data structures

Mathematics

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
from bisect import insort, bisect
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	s = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append((p[i], s[i]))
	l.sort()
	values = []
	ans = 0
	(i, j) = (n - 1, 0)
	if d < l[0][0]:
		print('0')
		continue
	while i >= 0:
		if l[i][0] > d:
			i -= 1
			continue
		ans = max(ans, l[i][1])
		while j < i and l[j][0] <= d - l[i][0]:
			insort(values, l[j][1])
			j += 1
		if i < j:
			values.pop(bisect(values, l[i][1]) - 1)
		if values:
			ans = max(ans, l[i][1] + values[-1])
		i -= 1
	print(ans)


from functools import cmp_to_key as ck
import bisect

def cp(a, b):
	if a[0] < b[0]:
		return -1
	if a[0] > b[0]:
		return 1
	return 0

def bs(arr, n, start, end, x):
	if start > end:
		return x
	half = (start + end) // 2
	mid = arr[half]
	if mid[0] <= n:
		return bs(arr, n, half + 1, end, half)
	else:
		return bs(arr, n, start, half - 1, x)

def codeforces(a, b, c, n):
	(res, ind) = ([], 0)
	for i in a:
		res.append([i, b[ind]])
		ind += 1
	res = sorted(res, key=ck(cp))
	dp = [0 for i in range(n)]
	curr = 0
	for i in range(n):
		if curr < res[i][1]:
			curr = res[i][1]
		dp[i] = curr
	ans = 0
	for i in range(n):
		if res[i][0] > c:
			break
		d = c - res[i][0]
		ind = bs(res, d, 0, n - 1, -1)
		if ind >= 0 and i:
			k = min(i - 1, ind)
			ans = max(res[i][1] + dp[k], ans)
		else:
			ans = max(ans, res[i][1])
	return ans
t = int(input())
for test in range(t):
	(n, d) = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	s = [int(i) for i in input().split()]
	print(codeforces(p, s, d, n))


from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	s = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append((p[i], s[i]))
	l.sort()
	pre = [0] * n
	max_sweet = -1
	for i in range(n):
		max_sweet = max(max_sweet, l[i][1])
		pre[i] = max_sweet
	ans = 0
	for i in range(n):
		if l[i][0] <= d:
			x = d - l[i][0]
			start = 0
			end = i - 1
			pos = -1
			while start <= end:
				mid = (start + end) // 2
				if l[mid][0] <= x:
					pos = mid
					start = mid + 1
				else:
					end = mid - 1
			sweetness = l[i][1]
			if pos != -1:
				sweetness = sweetness + pre[pos]
			ans = max(ans, sweetness)
	print(ans)


import sys
input = sys.stdin.readline
t = int(input().strip())
for __ in range(t):
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	s = list(map(int, input().split()))
	arr = [(0, 0)] + [(candy_price, candy_sweetness) for (candy_price, candy_sweetness) in zip(p, s)]
	arr.sort()
	smax = [0]
	for i in range(1, len(arr)):
		smax.append(max(smax[-1], arr[i][1]))
	left = 0
	right = len(arr) - 1
	final_result = 0
	while right >= 0 and arr[right][0] > d:
		right -= 1
	while right >= 0 and left < right:
		while left + 1 < right and arr[left + 1][0] + arr[right][0] <= d:
			left += 1
		final_result = max(final_result, smax[left] + arr[right][1])
		while right > 0 and arr[right - 1][0] == arr[right][0]:
			right -= 1
		right -= 1
	for i in range(right, 0, -1):
		final_result = max(final_result, smax[i - 1] + arr[i][1])
	print(final_result)


from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	p = [int(x) for x in input().split()]
	s = [int(x) for x in input().split()]
	arr = [[0, 0] for i in range(n)]
	for i in range(n):
		arr[i][0] = p[i]
		arr[i][1] = s[i]
	arr.sort()
	pre = [0] * n
	x = -1
	for i in range(n):
		x = max(x, arr[i][1])
		pre[i] = x
	ans = 0
	for i in range(n):
		if arr[i][0] <= d:
			x = d - arr[i][0]
			start = 0
			end = i - 1
			pos = -1
			while start <= end:
				mid = (start + end) // 2
				if arr[mid][0] <= x:
					pos = mid
					start = mid + 1
				else:
					end = mid - 1
			sw = arr[i][1]
			if pos != -1:
				sw = sw + pre[pos]
			ans = max(ans, sw)
	print(ans)


def maxswt():
	from bisect import insort, bisect
	for _ in range(int(input())):
		(N, D) = [int(x) for x in input().split()]
		P = [int(x) for x in input().split()]
		S = [int(x) for x in input().split()]
		data = [(P[i], S[i]) for i in range(N)]
		data.sort()
		values = []
		ans = 0
		(i, j) = (N, 0)
		while i:
			i -= 1
			if data[i][0] > D:
				continue
			ans = max(ans, data[i][1])
			while j < i and data[j][0] <= D - data[i][0]:
				insort(values, data[j][1])
				j += 1
			if i < j:
				values.pop(bisect(values, data[i][1]) - 1)
			if len(values):
				ans = max(ans, data[i][1] + values[-1])
		print(ans)
maxswt()


from bisect import bisect
for tci in range(int(input())):
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	s = list(map(int, input().split()))
	ps = [(p[i], s[i]) for i in range(n)]
	ps.sort()
	(result, pre) = ([0], [0])
	for i in range(n):
		(p[i], s[i]) = ps[i]
		pre.append(max(pre[i], s[i]))
		if p[i] <= d:
			result.append(s[i])
	if p[n - 1] + p[0] <= d:
		i = n - 1
		j = bisect(p, d - p[i])
	else:
		i = bisect(p, d - p[0], lo=1) - 1
		j = 0
	while i > j:
		while i > j and p[i] + p[j] <= d:
			j += 1
		result.append(s[i] + pre[j])
		i -= 1
	while i > 0:
		result.append(s[i] + pre[i])
		i -= 1
	print(max(result))


try:
	Test = int(input())
	for _ in range(Test):
		(N, D) = input().split()
		(N, D) = (int(N), int(D))
		PRICE_LIST = [int(x) for x in input().split()]
		Sweetness_LIST = [int(y) for y in input().split()]
		PAIRS = zip(PRICE_LIST, Sweetness_LIST)
		PAIRS = list(PAIRS)
		SORTED_PAIRS = sorted(PAIRS, key=lambda x: x[0])
		ANSWERS_LIST = [0] * N
		x = -1
		for j in range(N):
			x = max(x, SORTED_PAIRS[j][1])
			ANSWERS_LIST[j] = x
		ANS = 0
		for i in range(N):
			if SORTED_PAIRS[i][0] <= D:
				x = D - SORTED_PAIRS[i][0]
				F = 0
				E = i - 1
				POS = -1
				while F <= E:
					MID = (F + E) // 2
					if SORTED_PAIRS[MID][0] <= x:
						POS = MID
						F = MID + 1
					else:
						E = MID - 1
				SW = SORTED_PAIRS[i][1]
				if POS != -1:
					SW = SW + ANSWERS_LIST[POS]
				ANS = max(ANS, SW)
		print(ANS)
except EOFError as e:
	print(e)


import sys
input = sys.stdin.readline
t = int(input().rstrip())
for __ in range(t):
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	s = list(map(int, input().split()))
	arr = [(0, 0)] + [(cp, cs) for (cp, cs) in zip(p, s)]
	arr.sort()
	cmax = [0]
	for i in range(1, len(arr)):
		cmax.append(max(cmax[-1], arr[i][1]))
	lptr = 0
	rptr = len(arr) - 1
	res = 0
	while rptr >= 0 and arr[rptr][0] > d:
		rptr -= 1
	while rptr >= 0 and lptr < rptr:
		while lptr + 1 < rptr and arr[lptr + 1][0] + arr[rptr][0] <= d:
			lptr += 1
		res = max(res, cmax[lptr] + arr[rptr][1])
		while rptr > 0 and arr[rptr - 1][0] == arr[rptr][0]:
			rptr -= 1
		rptr -= 1
	for i in range(rptr, 0, -1):
		res = max(res, cmax[i - 1] + arr[i][1])
	print(res)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	s = list(map(int, input().split()))
	s_p = [[p[i], i] for i in range(n)]
	s_s = [[s[i], i] for i in range(n)]
	s_p = sorted(s_p)
	s_s = sorted(s_s)
	j = n - 1
	ans = 0
	for i in range(n):
		if p[i] <= d:
			ans = max(ans, s[i])
		while j >= 0 and (s_p[i][0] + p[s_s[j][1]] > d or s_p[i][1] == s_s[j][1]):
			j -= 1
		if j != -1:
			ans = max(ans, s[s_p[i][1]] + s_s[j][0])
	print(ans)


import bisect
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	s = list(map(int, input().split()))
	array = sorted(([p[i], s[i]] for i in range(n)))
	(dp, sweet) = ([], [])
	for i in range(n):
		dp.append(array[i][0])
		sweet.append(array[i][1])
	for i in range(1, n):
		sweet[i] = max(sweet[i], sweet[i - 1])
	ans = 0
	for i in range(n - 1, 0, -1):
		if array[i][0] < d:
			index = bisect.bisect_right(dp, d - array[i][0])
			if index == 0:
				ans = max(ans, sweet[i])
			else:
				ans = max(ans, array[i][1] + sweet[min(i - 1, index - 1)])
		if array[i][0] == d:
			ans = max(ans, array[i][1])
	if array[0][0] <= d:
		ans = max(ans, array[0][1])
	print(ans)


for tci in range(int(input())):
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	s = list(map(int, input().split()))
	ps = [(p[i], s[i]) for i in range(n)]
	ps.sort()
	(result, pre) = ([0], [0])
	for i in range(n):
		(p[i], s[i]) = ps[i]
		pre.append(max(pre[i], s[i]))
		if p[i] <= d:
			result.append(s[i])
	(i, d0) = (n - 1, d - p[0])
	while i > 0 and p[i] > d0:
		i -= 1
	j = 0
	while i > j:
		while i > j and p[i] + p[j] <= d:
			j += 1
		result.append(s[i] + pre[j])
		i -= 1
	while i > 0:
		result.append(s[i] + pre[i])
		i -= 1
	print(max(result))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
input = lambda : sys.stdin.readline().rstrip('\r\n')
readint = lambda : int(sys.stdin.readline().rstrip('\r\n'))
readints = lambda : map(int, sys.stdin.readline().rstrip('\r\n').split())
readstr = lambda : sys.stdin.readline().rstrip('\r\n')
readstrs = lambda : map(str, sys.stdin.readline().rstrip('\r\n').split())
readarri = lambda : [int(_) for _ in sys.stdin.readline().rstrip('\r\n').split()]
readarrs = lambda : [str(_) for _ in sys.stdin.readline().rstrip('\r\n').split()]

def solve():
	(n, money) = readints()
	combined = sorted(list(zip(readarri(), readarri())))
	if n == 1:
		print(0 if combined[0][0] > money else combined[0][1])
		return
	rM = [combined[0][1]]
	for i in range(1, n):
		rM.append(max(rM[-1], combined[i][1]))
	maxAns = 0
	for i in range(n - 1, -1, -1):
		if combined[i][0] > money:
			continue
		(l, r, ind, c) = (0, i - 1, -1, combined[i][1])
		while l <= r:
			m = l + (r - l >> 1)
			if combined[m][0] <= money - combined[i][0]:
				l = m + 1
				ind = m
			else:
				r = m - 1
		if ind != -1:
			c += rM[ind]
		maxAns = max(maxAns, c)
	print(maxAns)

def main():
	t = 1
	t = readint()
	for _ in range(t):
		solve()
main()


from bisect import *
from collections import *
from copy import copy, deepcopy
from functools import lru_cache, reduce
from heapq import *
from itertools import *
from math import ceil, factorial, floor, gcd, inf, log2 as lg, trunc
import operator as op
from random import *
import re
from statistics import median, mean
from string import ascii_lowercase as al, ascii_uppercase as au
import sys
sys.setrecursionlimit(25000)
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	ps = list(map(int, input().split()))
	ss = list(map(int, input().split()))
	li = {i for (i, p) in enumerate(ps) if p > d}
	ps = [p for (i, p) in enumerate(ps) if i not in li]
	ss = [s for (i, s) in enumerate(ss) if i not in li]
	if len(ps) == 0:
		print(0)
	elif len(ps) == 1:
		print(ss[0])
	else:
		li = sorted(range(len(ps)), key=ps.__getitem__)
		ps = [ps[i] for i in li]
		ss = [ss[i] for i in li]
		s1 = s2 = 0
		l1 = []
		l2 = []
		for (p, s) in zip(ps, ss):
			if s > s1:
				l1.append((p, s))
				(s1, s2) = (s, s1)
			elif s > s2:
				l2.append((p, s))
				s2 = s
		x = max(ss)
		for (i, (p, s)) in enumerate(l1):
			i1 = bisect(l1, (d - p, inf)) - 1
			if i1 == i:
				i1 -= 1
			i2 = bisect(l2, (d - p, inf)) - 1
			if i1 >= 0:
				x = max(x, s + l1[i1][1])
			if i2 >= 0:
				x = max(x, s + l2[i2][1])
		print(x)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	s = list(map(int, input().split()))
	arr = [[0, 0] for i in range(n)]
	for i in range(n):
		arr[i][0] = p[i]
		arr[i][1] = s[i]
	arr.sort()
	dp = [0] * n
	x = -1
	for i in range(n):
		x = max(x, arr[i][1])
		dp[i] = x
	ans = 0
	for i in range(n):
		if arr[i][0] <= d:
			x = d - arr[i][0]
			start = 0
			end = i - 1
			pos = -1
			while start <= end:
				mid = (start + end) // 2
				if arr[mid][0] <= x:
					pos = mid
					start = mid + 1
				else:
					end = mid - 1
			sw = arr[i][1]
			if pos != -1:
				sw = sw + dp[pos]
			ans = max(ans, sw)
	print(ans)


import bisect
for _ in range(int(input())):
	(N, D) = map(int, input().split())
	P = list(map(int, input().split()))
	S = list(map(int, input().split()))
	PS = list(zip(P, S))
	PS.sort()
	P = [x[0] for x in PS]
	S = [x[1] for x in PS]
	premax = [S[0]]
	for i in range(1, N):
		premax.append(max(S[i], premax[-1]))
	c = 0
	for i in range(N):
		if P[i] <= D:
			cost = D - P[i]
			bi = bisect.bisect_right(P, cost, hi=i) - 1 if i != 0 else -1
			c = max(c, S[i] + (premax[bi] if bi != -1 else 0))
	print(c)


from heapq import heapify, heappop, heappush
for _ in range(int(input())):
	(n, d) = list(map(int, input().split()))
	prices = list(map(int, input().split()))
	sweet = list(map(int, input().split()))
	arr = [[0, 0] for _ in range(n)]
	for i in range(n):
		arr[i][0] = prices[i]
		arr[i][1] = sweet[i]
	arr.sort()
	pre = [0] * n
	x = -1
	for i in range(n):
		x = max(x, arr[i][1])
		pre[i] = x
	ans = 0
	for i in range(n):
		if arr[i][0] <= d:
			x = d - arr[i][0]
			start = 0
			end = i - 1
			pos = -1
			while start <= end:
				mid = (start + end) // 2
				if arr[mid][0] <= x:
					pos = mid
					start = mid + 1
				else:
					end = mid - 1
			sw = arr[i][1]
			if pos != -1:
				sw = sw + pre[pos]
			ans = max(ans, sw)
	print(ans)


import sys
from collections import deque

def read(lst=False):
	line = sys.stdin.readline().rstrip()
	if ' ' in line or lst:
		return map(int, line.split())
	return line
T = int(read())
for t in range(T):
	(N, D) = read()
	P = list(read(True))
	S = list(read(True))
	merge = [[P[i], S[i]] for i in range(N)]
	merge.sort()
	if merge[0][0] > D:
		print(0)
		continue
	q = [0]
	maxAns = merge[0][1]
	for i in range(1, N):
		temp = merge[i][1]
		while q and merge[q[-1]][0] + merge[i][0] > D:
			q.pop()
		if q:
			temp += merge[q[-1]][1]
		elif merge[i][0] > D:
			temp = 0
		maxAns = max(maxAns, temp)
		merge[i][1] = max(merge[i][1], merge[i - 1][1])
		q.append(i)
	print(maxAns)
sys.exit()


import bisect
import heapq
n_testcase = int(input())
for testcase in range(n_testcase):
	(n, budget) = (int(x) for x in input().split())
	prices = [int(x) for x in input().split()]
	sweetnesses = [int(x) for x in input().split()]
	candies = list(zip(prices, sweetnesses))
	candies.sort()
	prices = [price for (price, sweetness) in candies]
	sweetnesses = [sweetness for (price, sweetness) in candies]
	if any((price <= budget for price in prices)):
		max_sweetness = max((sweetness for (price, sweetness) in candies if price <= budget))
	else:
		max_sweetness = 0
	heap = []
	k = 0
	for (i, (price, sweetness)) in list(enumerate(candies))[::-1]:
		if budget - price < prices[0]:
			continue
		while k < n and prices[k] <= budget - price:
			heapq.heappush(heap, -sweetnesses[k])
			k += 1
		poped = False
		if i <= k and -heap[0] == sweetness:
			heapq.heappop(heap)
			poped = True
		if heap:
			max_sweetness = max(max_sweetness, sweetness + -heap[0])
		if poped:
			heapq.heappush(heap, -sweetness)
	print(max_sweetness)


from sys import stdin
input = stdin.readline

def b_s(key, l, h):
	ans = 0
	while l <= h:
		mid = (l + h) // 2
		if a[mid][0] <= key:
			ans = max(ans, pf[mid])
			l = mid + 1
		else:
			h = mid - 1
	return ans

def answer():
	ans = 0
	for i in range(n - 1, -1, -1):
		x = a[i][0]
		if x > d:
			continue
		m_v = b_s(d - x, 0, i - 1)
		ans = max(ans, a[i][1] + m_v)
	return ans
for T in range(int(input())):
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	s = list(map(int, input().split()))
	a = [[p[i], s[i]] for i in range(n)]
	a.sort(key=lambda x: x[0])
	pf = [a[0][1]]
	for i in range(1, n):
		pf.append(max(pf[-1], a[i][1]))
	print(answer())


from bisect import *
from collections import *
from copy import copy, deepcopy
from functools import lru_cache, reduce
from heapq import *
from itertools import *
from math import ceil, factorial, floor, gcd, inf, log2 as lg, trunc
import operator as op
from random import *
import re
from statistics import median, mean
from string import ascii_lowercase as al, ascii_uppercase as au
import sys
sys.setrecursionlimit(25000)
cin = sys.stdin
read = cin.readline
cout = sys.stdout
write = cout.write
rir = lambda : range(int(read()))
ir = lambda : int(read())
mir = lambda : map(int, read().split())
lmir = lambda : list(map(int, read().split()))
res = []
for _ in rir():
	(n, d) = mir()
	ps = lmir()
	ss = lmir()
	li = {i for (i, p) in enumerate(ps) if p > d}
	ps = [p for (i, p) in enumerate(ps) if i not in li]
	ss = [s for (i, s) in enumerate(ss) if i not in li]
	if len(ps) == 0:
		res.append(0)
	elif len(ps) == 1:
		res.append(ss[0])
	else:
		li = sorted(range(len(ps)), key=ps.__getitem__)
		ps = [ps[i] for i in li]
		ss = [ss[i] for i in li]
		s1 = s2 = 0
		l1 = []
		l2 = []
		for (p, s) in zip(ps, ss):
			if s > s1:
				l1.append((p, s))
				(s1, s2) = (s, s1)
			elif s > s2:
				l2.append((p, s))
				s2 = s
		x = max(ss)
		for (i, (p, s)) in enumerate(l1):
			i1 = bisect(l1, (d - p, inf)) - 1
			if i1 == i:
				i1 -= 1
			i2 = bisect(l2, (d - p, inf)) - 1
			if i1 >= 0:
				x = max(x, s + l1[i1][1])
			if i2 >= 0:
				x = max(x, s + l2[i2][1])
		res.append(x)
write('\n'.join(map(str, res)))


import bisect
import sys
input = sys.stdin.readline

def solve(a, b, n, d):
	mat = sorted([[a[i], b[i]] for i in range(n)])
	dp = [0] * n
	aa = [0] * n
	for i in range(n):
		aa[i] = mat[i][0]
		dp[i] = mat[i][1]
	for i in range(1, n):
		dp[i] = max(dp[i], dp[i - 1])
	ans = 0
	for i in range(n - 1, 0, -1):
		if mat[i][0] < d:
			re = d - mat[i][0]
			ind = bisect.bisect_right(aa, re)
			if ind == 0:
				ans = max(ans, dp[i])
			else:
				ind = min(i - 1, ind - 1)
				ans = max(ans, mat[i][1] + dp[ind])
		if mat[i][0] == d:
			ans = max(ans, mat[i][1])
	if mat[0][0] <= d:
		ans = max(ans, mat[0][1])
	return ans
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = str(solve(a, b, n, d))
	sys.stdout.write(p + '\n')


import bisect

def solve(a, b, n, d):
	mat = sorted([[a[i], b[i]] for i in range(n)])
	dp = [0] * n
	aa = [0] * n
	for i in range(n):
		aa[i] = mat[i][0]
		dp[i] = mat[i][1]
	for i in range(1, n):
		dp[i] = max(dp[i], dp[i - 1])
	ans = 0
	for i in range(n - 1, 0, -1):
		if mat[i][0] < d:
			re = d - mat[i][0]
			ind = bisect.bisect_right(aa, re)
			if ind == 0:
				ans = max(ans, dp[i])
			else:
				ind = min(i - 1, ind - 1)
				ans = max(ans, mat[i][1] + dp[ind])
		if mat[i][0] == d:
			ans = max(ans, mat[i][1])
	if mat[0][0] <= d:
		ans = max(ans, mat[0][1])
	return ans
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(solve(a, b, n, d))