It is the Indian version of the famous heist “The Italian Job”. N robbers have already broken into the National Museum and are just about to get inside the main vault which is full of jewels. They were lucky that just as they broke into the museum, the guard was leaving the museum for exactly G minutes. But there are other problems too. The main vault has heat sensors that if at any moment of time there are more than two people present in the vault, the alarm goes off.  

To collect the jewels, the i^{th} robber needs to be inside the vault for exactly A[i] minutes, 0 <= i < N, in one continuous stretch. As guard will return after G minutes, they have to finish their tasks within G minutes. The robbers want to know if there exists any arrangement such that demands of each robber is satisfied and also they are not caught?

Gotchas 

If a robber goes inside the vault at a time "X" and at the same time another robber comes out, it's equivalent to saying they were never in the vault at the same time. 

Similarly, when the guard gets inside vault at time G and a robber comes out exactly at time G, the guard will not be able see the robber.

Input Format

The first line contains an integer T denoting the number of testcases. T testcases follow.
Each testcase consists of two lines. First line contains two space separated integers denoting N and G denoting the number of thieves and duration for which guard leaves the museum. 

The next line contains N space separated numbers where the ith integer, A[i] 
represents the time the i^{th} robber needs to be in the vault.

Constraints

1 <= T <= 20 

1 <= N <= 100 

0 <= G <= 1000000 ($10^{6}$) 

0 <= A[i] <= 100  

Output Format

For each testcase print YES if there exists such an arrangement or NO otherwise in a newline.  

Sample Input
2
3 4
2 4 2
3 2
2 4 2

Sample Output
YES
NO

Explanation

Test case #00: In first testcase, one possible arrangement is: 

at t=0, robber1 goes inside and comes out at t=2 

at t=0, robber2 goes inside and comes out at t=4 

at t=2, robber3 goes inside and comes out at t=4  

Test case #01: No possible arrangement is possible in second testcase.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
import itertools

def nzerolast(l):
	for i in range(len(l) - 1, -1, -1):
		if l[i] > 0:
			return i
	return 0
T = int(input())
for _ in range(T):
	(N, G) = map(int, input().split())
	L = list(itertools.repeat(0, G + 1))
	nl = list(map(int, input().split()))
	L[0] = 1
	for num in nl:
		for g in range(G, num - 1, -1):
			L[g] += L[g - num]
	can = nzerolast(L)
	print('YES' if sum(nl) - can <= G else 'NO')


import sys
import re

def Knapsack01(weight, value, maxweight):
	B = [[0 for i in range(maxweight + 1)] for j in range(len(weight) + 1)]
	for i in range(1, len(weight) + 1):
		for w in range(maxweight + 1):
			if weight[i - 1] <= w:
				if value[i - 1] + B[i - 1][w - weight[i - 1]] > B[i - 1][w]:
					B[i][w] = value[i - 1] + B[i - 1][w - weight[i - 1]]
				else:
					B[i][w] = B[i - 1][w]
			else:
				B[i][w] = B[i - 1][w]
	return B[len(weight)][maxweight]
rule = re.compile('\\d+')
T = int(sys.stdin.readline().rstrip('\n'))
for t in range(T):
	[N, G] = [int(i) for i in rule.findall(sys.stdin.readline())]
	W = [int(i) for i in rule.findall(sys.stdin.readline()) if i != '0']
	totalweight = sum(W)
	if G >= totalweight:
		print('YES')
	elif G < totalweight / 2:
		print('NO')
	elif totalweight - Knapsack01(W, W, G) <= G:
		print('YES')
	else:
		print('NO')


list = None
memo = None

def fit(N, G):
	if N <= 0:
		return 0
	elif (N, G) in memo:
		return memo[N, G]
	else:
		if list[-N] > G:
			result = fit(N - 1, G)
		elif list[-N] == G:
			result = G
		else:
			result = list[-N] + fit(N - 1, G - list[-N])
			if result < G:
				result = max(result, fit(N - 1, G))
		memo[N, G] = result
		return result
for T in range(int(input())):
	(N, G) = map(int, input().split())
	R = sorted(map(int, input().split()), reverse=True)
	s = sum(R)
	if s > 2 * G:
		print('NO')
	elif s > G:
		list = R
		memo = dict()
		f = fit(N, G)
		if s - f > G:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


import sys
import collections

def resolve(_list, _g):
	_list.sort()
	sumval = sum(_list)
	if sumval > _g * 2 or _list[-1] > _g:
		return 'NO'
	if sumval - _list[-1] <= _g and _list[-1] <= _g:
		return 'YES'
	while _list[0] == 0:
		_list.pop(0)
	reso = Resolve(_list, _g)
	if reso.result == True:
		return 'YES'
	else:
		return 'NO'

class Resolve:

	def __init__(self, _list, g):
		self.dic = {}
		maxitem = _list[-1]
		self.count = collections.Counter(_list)
		self.list_length = len(_list)
		self.list = _list
		self.g = g
		self.usedflag = {}
		self.keylist = []
		for key in self.count.keys():
			self.usedflag[key] = 0
			self.keylist.append(key)
		self.keylist.sort(reverse=True)
		self.sumval = sum(self.list)
		self.result = self.solveIndianJob(0, 0)

	def solveIndianJob(self, value, depth):
		if value <= self.g and self.sumval - value <= self.g:
			return True
		if value > self.g:
			return False
		if depth == len(self.keylist):
			return False
		for i in range(self.count[self.keylist[depth]], -1, -1):
			newvalue = value + self.keylist[depth] * i
			ret = self.solveIndianJob(newvalue, depth + 1)
			if ret == True:
				return True
		return False

	def getSubList(self, length, depth):
		if depth >= self.list_length:
			return []
		count = self.count
		dic = self.dic
		if length in dic:
			return dic[length]
		results = []
		if length == 0:
			dic[length] = results
			return results
		print('len={0}  '.format(length))
		for (index, item) in enumerate(count.items()):
			if item[0] < length and self.usedflag[item[0]] < item[1]:
				self.usedflag[item[0]] += 1
				ret_vals = self.getSubList(length - item[0], depth + 1)
				self.usedflag[item[0]] -= 1
				if len(ret_vals) == 0:
					tmpdic = {item[0]: 1}
					results.append(tmpdic)
				else:
					for ret in ret_vals:
						if item[0] in ret:
							if item[1] - ret[item[0]] > 0:
								newdict = ret.copy()
								newdict[item[0]] += 1
								results.append(newdict)
							else:
								pass
						else:
							newdict = ret.copy()
							newdict[item[0]] = 1
							results.append(newdict)
			elif item[0] == length:
				tmpdic = {item[0]: 1}
				results.append(tmpdic)
		dic[length] = results
		print('len={0}  :  {1}'.format(length, results))
		return results

def readFromStdin():
	r = sys.stdin.readline
	text = r()
	t = int(text)
	for i in range(t):
		text = r()
		(n, g) = map(int, text.split())
		text = r()
		readlist = list(map(int, text.split()))
		print(resolve(readlist, g))

def test():
	tests = [([1234, 23, 45, 67, 99, 900], 1400), ([0, 0, 300, 100, 100, 300, 50], 450), ([300, 100, 100, 300, 50], 450), ([30, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 2, 1, 1, 23, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 3, 3, 3, 3, 10], 100), ([300, 300, 300], 500)]
	for test in tests:
		print('test case {0}'.format(test))
		tmp = resolve(test[0], test[1])
		print(tmp)
readFromStdin()


T = int(input())
while T > 0:
	T -= 1
	line = input().split()
	N = int(line[0])
	G = int(line[1])
	line = input().split()
	arr = [int(num) for num in line]
	tot = sum(arr)
	arr.sort(reverse=True)
	mem1 = 0
	mem2 = 0
	st = {0}
	for i in arr:
		tst = set()
		for elem in st:
			tst.add(elem + i)
		st = st.union(tst)
	noans = True
	for num in st:
		if max(num, tot - num) <= G:
			print('YES')
			noans = False
			break
	if noans:
		print('NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


t = int(input())
for _ in range(t):
	(n, G) = list(map(int, input().split()))
	lis = list(map(int, input().split()))
	S = sum(lis)
	if S <= G:
		print('YES')
		continue
	P = [[0 for y in range(G + 1)] for x in range(n + 1)]
	for x in range(1, n + 1):
		for y in range(G + 1):
			P[x][y] = max(P[x - 1][y], 0 if y - lis[x - 1] < 0 else P[x - 1][y - lis[x - 1]] + lis[x - 1])
	if S - P[n][G] <= G:
		print('YES')
	else:
		print('NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


tn = int(input())

def _has_solution_nocache(a, i, l1, l2, cache):
	if i == len(a):
		return True
	if l1 >= a[i] and _has_solution(a, i + 1, l1 - a[i], l2, cache):
		return True
	if l2 >= a[i] and _has_solution(a, i + 1, l1, l2 - a[i], cache):
		return True
	return False

def _has_solution(a, i, l1, l2, cache):
	if (i, l1, l2) in cache:
		return cache[i, l1, l2]
	sol = _has_solution_nocache(a, i, l1, l2, cache)
	cache[i, l1, l2] = sol
	return sol

def has_solution(a, g):
	cache = {}
	return _has_solution(a, 0, g, g, cache)
for _ in range(tn):
	(n, g) = [x for x in map(int, input().split())]
	a = [x for x in map(int, input().split())]
	if has_solution(a, g):
		print('YES')
	else:
		print('NO')


def main():
	t = int(input())
	while t:
		ng = input().split()
		n = int(ng[0])
		g = int(ng[1])
		printed = 0
		a = input().split()
		summie = 0
		for i in range(0, n):
			a[i] = int(a[i])
			if a[i] > g:
				print('NO')
				printed = 1
				break
			summie += a[i]
			if summie / 2 > g:
				print('NO')
				printed = 1
				break
		if printed == 0:
			k = g
			c = [[0] * (n + 1) for i in range(k + 1)]
			a.insert(0, 0)
			for i in range(1, n + 1):
				for j in range(1, k + 1):
					if j - a[i] >= 0:
						c[j][i] = max(a[i] + c[j - a[i]][i - 1], c[j][i - 1])
					else:
						c[j][i] = c[j][i - 1]
			block_1 = c[k][n]
			block_2 = summie - block_1
			if block_2 <= g:
				print('YES')
			else:
				print('NO')
		t -= 1
main()


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


T = int(input())
for i in range(T):
	(n, G) = input().split()
	n = int(n)
	G = int(G)
	times = list(map(int, input().split()))
	times.sort()
	if times[n - 1] > G:
		print('NO')
		continue
	sumTimes = sum(times)
	if sumTimes > G * 2:
		print('NO')
		continue
	if sumTimes == 0:
		print('YES')
		continue
	isSum = [[False for x in range(G + 2)] for y in range(n + 1)]
	for i in range(n + 1):
		isSum[i][0] = True
	for i in range(1, G + 1):
		for j in range(1, n + 1):
			isSum[j][i] = isSum[j - 1][i]
			if i >= times[j - 1]:
				isSum[j][i] = isSum[j][i] or isSum[j - 1][i - times[j - 1]]
	print('YES' if isSum[n][min(G, sumTimes)] else 'NO')


import logging
import array
import fileinput
nivel_log = logging.ERROR
logger_cagada = None

def imprime_matrix(matrix, buf):
	for fila in matrix:
		for elem in fila:
			buf += '%s\t' % elem
		buf += '\n'
	return buf

def es_suma_posible(numeros, suma):
	num_numeros = 0
	numeros_ordenados = []
	matrix_posiblidades = None
	buf = ''
	num_numeros = len(numeros)
	matrix_posiblidades = [[False for i in range(num_numeros + 1)] for j in range(suma + 1)]
	matrix_posiblidades[0][:] = [True] * (num_numeros + 1)
	matrix_posiblidades[:][0] = [False] * (suma + 1)
	numeros_ordenados = numeros
	logger_cagada.debug('los numeros ordenados %s' % numeros_ordenados)
	for suma_actual in range(suma + 1):
		for (idx_num_actual, numero_actual) in enumerate(numeros_ordenados, start=1):
			matrix_posiblidades[suma_actual][idx_num_actual] = matrix_posiblidades[suma_actual][idx_num_actual - 1]
			if numero_actual <= suma_actual:
				matrix_posiblidades[suma_actual][idx_num_actual] |= matrix_posiblidades[suma_actual - numero_actual][idx_num_actual - 1]
	logger_cagada.debug('la matrix de posiblidades\n%s' % imprime_matrix(matrix_posiblidades, buf))
	return matrix_posiblidades[suma][num_numeros]

def blw_job_main(necesidades_rateros, siesta_guardia):
	total_necedades_rat = 0
	minimo_formable = 0
	total_necedades_rat = sum(necesidades_rateros)
	if total_necedades_rat > siesta_guardia * 2:
		return False
	if necesidades_rateros[-1] > siesta_guardia:
		return False
	minimo_formable = total_necedades_rat - siesta_guardia
	logger_cagada.debug('lo minimo q c debe poder formar es %u' % minimo_formable)
	for num_prueba_formable in reversed(list(range(minimo_formable, siesta_guardia + 1))):
		resultado = False
		logger_cagada.debug('probando si %u se puede formar' % num_prueba_formable)
		resultado = es_suma_posible(necesidades_rateros, num_prueba_formable)
		logger_cagada.debug('con suma %u c pudo? %s' % (num_prueba_formable, resultado))
		if resultado:
			return True
	return False
resultado = False
suma = 0
num_casos_uso = 0
num_ladronzuelos = 0
siesta_guardia = 0
num_linea = 0
necesidades_rateros = array.array('I')
linea = []
logging.basicConfig(level=nivel_log)
logger_cagada = logging.getLogger('asa')
logger_cagada.setLevel(nivel_log)
lineas = list(fileinput.input())
num_casos_uso = int(lineas[0])
num_linea = 1
for _ in range(num_casos_uso):
	necesidades_rateros = array.array('I')
	(num_ladronzuelos, siesta_guardia) = [int(x.strip()) for x in lineas[num_linea].split(' ')]
	num_linea += 1
	necesidades_rateros.extend(sorted([int(x.strip()) for x in lineas[num_linea].split(' ')]))
	num_linea += 1
	assert num_ladronzuelos == len(necesidades_rateros)
	logger_cagada.debug('el num de ladrones %u, la siesta del guardia %u' % (num_ladronzuelos, siesta_guardia))
	logger_cagada.debug('las necesidades d los rateros %s' % necesidades_rateros)
	resultado = blw_job_main(necesidades_rateros, siesta_guardia)
	logger_cagada.debug('la cagada es %s' % resultado)
	if resultado:
		print('YES')
	else:
		print('NO')


def rectify(a, b, total_time):
	time_a = sum(a)
	time_b = sum(b)
	a_too_big = time_a > total_time
	if a_too_big:
		diff = time_a - total_time
	else:
		diff = time_b - total_time
	for i in range(len(a)):
		for j in range(len(b)):
			if a[i] != b[j]:
				if a_too_big and a[i] > b[j] and (a[i] - b[j] <= diff):
					diff -= a[i] - b[j]
					(a[i], b[j]) = (b[j], a[i])
				elif not a_too_big and b[j] > a[i] and (b[j] - a[i] <= diff):
					diff -= b[j] - a[i]
					(a[i], b[j]) = (b[j], a[i])
				if diff <= 0:
					return (sum(a), sum(b))
	return (sum(a), sum(b))

def robbery_possible(robber_times, total_time):
	a = []
	b = []
	time_a = time_b = 0
	for robber_time in reversed(sorted(robber_times)):
		if time_a <= time_b:
			a.append(robber_time)
			time_a += robber_time
		else:
			b.append(robber_time)
			time_b += robber_time
		if time_a > total_time or time_b > total_time:
			(time_a, time_b) = rectify(a, b, total_time)
			if time_a > total_time or time_b > total_time:
				return 'NO'
	return 'YES'
tests_cnt = int(input().strip())
for _ in range(tests_cnt):
	(num_robbers, total_time) = [int(n) for n in input().strip().split()]
	robber_times = [int(n) for n in input().strip().split()]
	print(robbery_possible(robber_times, total_time))


from copy import copy

def IsPossible(N, G, A):
	sumTime = sum(A)
	if G >= sumTime:
		return True
	elif G < sumTime // 2:
		return False
	toVisit = set([0, A[0]])
	for i in range(1, N):
		curVal = A[i]
		newAdd = set([])
		for v in toVisit:
			newAdd.add(curVal + v)
		toVisit.update(newAdd)
	for n in toVisit:
		if n <= G and sumTime - n <= G:
			return True
	return False
T = int(input())
for _ in range(T):
	(N, G) = tuple(map(int, input().split()))
	A = tuple(map(int, input().split()))
	print('YES' if IsPossible(N, G, A) else 'NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


import sys

def indianJob(A, G):
	if A[0] > G:
		return False
	dp = [False for j in range(G + 1)]
	dp[A[0]] = True
	s = A[0]
	for idx in range(1, N):
		s += A[idx]
		newDP = [False] * (G + 1)
		for i in range(G + 1):
			if dp[i]:
				diff = i + A[idx]
				if (s + diff) / 2 <= G:
					newDP[diff] = True
				diff = abs(i - A[idx])
				if (s + diff) / 2 <= G:
					newDP[diff] = True
		dp = newDP
	return True if True in dp else False
f = sys.stdin
T = int(f.readline())
for i in range(T):
	tmp = f.readline().split()
	N = int(tmp[0])
	G = int(tmp[1])
	tmp = f.readline().split()
	A = [int(tmp[j]) for j in range(N)]
	if indianJob(A, G):
		print('YES')
	else:
		print('NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


for _ in range(int(input())):
	(N, G) = [int(x) for x in input().split(' ')]
	A = [int(x) for x in input().split(' ')]
	s = sum(A)
	P = [[False] * (N + 1) for _ in range(s // 2 + 1)]
	P[0] = [True] * (N + 1)
	for i in range(1, s // 2 + 1):
		for j in range(1, N + 1):
			if i - A[j - 1] < 0:
				P[i][j] = P[i][j - 1]
			else:
				P[i][j] = P[i][j - 1] or P[i - A[j - 1]][j - 1]
	s1 = s // 2 - [x[N] for x in P[::-1]].index(True)
	s2 = s - s1
	if G < max(s1, s2):
		print('NO')
	else:
		print('YES')


for _ in range(int(input().strip())):
	(N, G) = map(int, input().strip().split())
	A = sorted(list(map(int, input().strip().split())))
	if A[N - 1] > G or sum(A) > 2 * G:
		print('NO')
		continue
	states = set([0])
	[states.add(i + x) for i in A for x in states.copy() if i + x <= G]
	print('YES') if sum(A) - max(states) <= G else print('NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


import sys
numTests = int(input().strip())
for _ in range(numTests):
	(numRobbers, guard) = input().strip().split(' ')
	(numRobbers, guard) = [int(numRobbers), int(guard)]
	robbers = [int(robber) for robber in input().strip().split(' ')]
	robbers.sort(reverse=True)
	p1 = [0]
	p2 = [0]
	s1 = s2 = 0
	diff = 0
	for r in robbers:
		maxabs = maxreal = sw1 = sw2 = ind1 = ind2 = sys.maxsize
		first = True
		i = 0
		for num1 in p1:
			j = 0
			for num2 in p2:
				d = (num1 - num2) * -2
				tempDiff = diff + d
				ans = tempDiff + r
				if abs(ans) < maxabs:
					maxabs = abs(ans)
					maxreal = ans
					sw1 = num1
					sw2 = num2
					ind1 = i
					ind2 = j
					first = True
				ans = tempDiff - r
				if abs(ans) < maxabs:
					maxabs = abs(ans)
					maxreal = ans
					sw1 = num1
					sw2 = num2
					ind1 = i
					ind2 = j
					first = False
				j += 1
			i += 1
		if sw1 == 0 and sw2 == 0:
			r = r
		elif sw1 == 0:
			p1.append(p2[ind2])
			s1 += p2[ind2]
			s2 -= p2[ind2]
			del p2[ind2]
		elif sw2 == 0:
			p2.append(p1[ind1])
			s1 -= p1[ind1]
			s2 += p1[ind1]
			del p1[ind1]
		else:
			s1 += p2[ind2]
			s1 -= p1[ind1]
			s2 += p1[ind1]
			s2 -= p2[ind2]
			temp = p1[ind1]
			p1[ind1] = p2[ind2]
			p2[ind2] = temp
		if first:
			p1.append(r)
			s1 += r
		else:
			p2.append(r)
			s2 += r
		diff = s1 - s2
		p1.sort(reverse=True)
		p2.sort(reverse=True)
	m = max(s1, s2)
	if m > guard:
		print('NO')
	else:
		print('YES')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


for _ in range(int(input())):
	(n, g) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	dp = [set([]) for x in range(len(a))]
	if a[0] <= g:
		dp[0] = set([0, a[0]])
	else:
		dp[0] = set([0])
	for x in range(1, len(a)):
		for y in list(dp[x - 1]):
			dp[x].add(y)
			if y + a[x] <= g:
				dp[x].add(y + a[x])
	print('YES' if sum(a) - max(dp[-1]) <= g else 'NO')


T = int(input().strip())
for run in range(T):
	(N, G) = map(int, input().strip().split())
	A = [int(i) for i in input().strip().split()]
	if max(A) > G or sum(A) > 2 * G:
		print('NO')
	elif sum(A) < G:
		print('YES')
	else:
		states = set([0])
		for i in A:
			for x in list(states):
				if i + x <= G:
					states.add(x + i)
		if sum(A) - max(states) <= G:
			print('YES')
		else:
			print('NO')


import unittest

class TheIndianJob:
	memoize = {}

	def __init__(self, g, A):
		self._g = g
		self._A = A

	def calculate(self):
		self._A.sort(reverse=True)
		return self.recursive_formulation(self._g, self._g, self._A[:])

	def recursive_formulation(self, l1, l2, A):
		if l1 < l2:
			(l1, l2) = (l2, l1)
		if l1 < 0 or l2 < 0:
			return False
		if sum(A) > l1 + l2:
			return False
		if len(A) == 0:
			return True
		if len(A) == 1:
			if A[0] <= l1 or A[0] <= l2:
				return True
			else:
				return False
		if sum(A) == l1 or sum(A) == l2:
			return True
		key = '{}_{}_{}'.format(l1, l1, '_'.join(['{}'.format(x) for x in A]))
		if key in self.memoize:
			return self.memoize.get(key)
		first_el = A[0]
		remaining_array = A[1:]
		possibility = self.recursive_formulation(l1 - first_el, l2, remaining_array) or self.recursive_formulation(l1, l2 - first_el, remaining_array)
		self.memoize[key] = possibility
		return possibility

class TestTheIndianJob(unittest.TestCase):

	def test1(self):
		tij = TheIndianJob(4, [2, 4, 2])
		self.assertEqual(tij.calculate(), True)

	def test2(self):
		tij = TheIndianJob(2, [2, 4, 2])
		self.assertEqual(tij.calculate(), False)

	def test3(self):
		tij = TheIndianJob(4, [5, 1, 2])
		self.assertEqual(tij.calculate(), False)

	def test4(self):
		tij = TheIndianJob(9, [4, 4, 3, 3, 3])
		self.assertEqual(tij.calculate(), True)

	def test5(self):
		tij = TheIndianJob(9, [4, 4, 4, 3, 3])
		self.assertEqual(tij.calculate(), False)

	def test6(self):
		tij = TheIndianJob(11, [10])
		self.assertEqual(tij.calculate(), True)
n = int(input().strip())
for i in range(n):
	(r_count, g) = map(int, input().strip().split())
	A = [int(el) for el in input().strip().split()]
	tij = TheIndianJob(g, A)
	if tij.calculate():
		print('YES')
	else:
		print('NO')


def robbery_possible(guard_time, thief_times):
	thief_times = sorted(thief_times)
	total_times = set([0])
	t_sum = 0
	t_max = 0
	for t_thief in thief_times:
		t_sum += t_thief
		for t_total in list(total_times):
			t_cur = t_total + t_thief
			if t_cur <= guard_time:
				if t_cur > t_max:
					t_max = t_cur
				total_times.add(t_cur)
			else:
				break
	return t_sum - t_max <= guard_time
n_tests = int(input())
for t_n in range(n_tests):
	(N, G) = map(int, input().split(' '))
	thief_times = list(map(int, input().split(' ')))
	if robbery_possible(G, thief_times):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(N, G) = map(int, input().split())
	minutes = sorted(list(map(int, input().split())))
	if max(minutes) > G or sum(minutes) > 2 * G:
		print('NO')
	else:
		sums = set([0])
		for m in minutes:
			for s in sorted(sums):
				if m + s > G:
					break
				sums.add(m + s)
		print('NO' if sum(minutes) - max(sums) > G else 'YES')


num_tests = int(input())
for _ in range(num_tests):
	(num_thieves, duration) = map(int, input().split())
	thief_times = [int(i) for i in input().split()]
	total_thief_time = sum(thief_times)
	if total_thief_time > 2 * duration:
		print('NO')
		continue
	if total_thief_time < duration:
		print('YES')
		continue
	prev_can_sum_to = [True] + [False] * duration
	for time in thief_times:
		can_sum_to = [True]
		for i in range(1, duration + 1):
			can_sum_to.append(prev_can_sum_to[i] or (i - time >= 0 and prev_can_sum_to[i - time]))
		prev_can_sum_to = can_sum_to
	if any(can_sum_to[total_thief_time - duration:]):
		print('YES')
	else:
		print('NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


number = int(input())
for i in range(number):
	l1 = input().split()
	n = int(l1[0])
	w = int(l1[1])
	l2 = input().split()
	for j in range(n):
		l2[j] = int(l2[j])
	if sum(l2) > 2 * w or max(l2) > w:
		print('NO')
	else:
		table = [[0 for column in range(n + 1)] for row in range(w + 1)]
		for row in range(1, w + 1):
			for column in range(n):
				if l2[column] <= row:
					table[row][column + 1] = max(table[row - l2[column]][column] + l2[column], table[row][column])
		if sum(l2) - table[w][n] <= w:
			print('YES')
		else:
			print('NO')


def parseInput(f):
	return [f(x) for x in input().split()]

def solve(arr, pos, limit, d):
	if (pos, limit) in d:
		return d[pos, limit]
	if limit == 0:
		return 0
	if pos == 0:
		if arr[pos] <= limit:
			return arr[pos]
		else:
			return 0
	else:
		(first, second) = (0, 0)
		if arr[pos] <= limit:
			first = arr[pos] + solve(arr, pos - 1, limit - arr[pos], d)
		second = solve(arr, pos - 1, limit, d)
		d[pos, limit] = max(first, second)
		return d[pos, limit]
t = int(input())
for _ in range(t):
	(n, g) = parseInput(int)
	arr = parseInput(int)
	answer = True
	if all((value <= g for value in arr)):
		total = sum(arr)
		d = {}
		m = solve(arr, n - 1, g, d)
		if total - m <= g:
			pass
		else:
			answer = False
	else:
		answer = False
	print('YES' if answer else 'NO')


def calc(n, g, A):
	total = sum(A)
	if total > 2 * g:
		return False
	S = set([0])
	limit = total - g
	for el in A:
		listS = list(S)
		for elem in listS:
			newElem = elem + el
			if newElem <= g:
				S.add(newElem)
				if limit <= newElem:
					return True
	return False

def main():
	T = int(input())
	for t0 in range(T):
		(n, g) = [el for el in map(int, input().rstrip().split(' '))]
		A = [el for el in map(int, input().rstrip().split(' '))]
		bool = calc(n, g, A)
		print('YES' if bool else 'NO')
main()


def findMatch(numList, target):
	minTarget = sum(numList) - target
	if minTarget > target:
		return False
	if target == 0:
		return True
	possibleArray = [0 for i in range(target)]
	possibleArray[0] = 1
	for num in numList:
		for i in range(target - 1, -1, -1):
			if possibleArray[i] == 1:
				newPossibility = i + num
				if newPossibility >= minTarget and newPossibility <= target:
					return True
				if newPossibility < target:
					possibleArray[newPossibility] = 1
	return False

def unitTest():
	print(findMatch([2, 4, 2], 4))
	print(findMatch([2, 4, 2], 2))
numTest = int(input())
for i in range(numTest):
	(n, target) = list(map(int, input().split()))
	numList = list(map(int, input().split()))
	if findMatch(numList, target) == True:
		print('YES')
	else:
		print('NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


T = int(input())
for t in range(T):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	possible = False
	sm = sum(A)
	if max(A) <= G and sm <= 2 * G:
		bits = [[0] * (sm + 1) for s in range(N + 1)]

		def getbit(ix, sm):
			return bits[ix][sm] != 0

		def setbit(ix, sm, bitval):
			bits[ix][sm] = bitval
		for n in range(N + 1):
			bits[n][0] = 1
		for n in range(1, N + 1):
			a = A[n - 1]
			for s in range(1, sm + 1):
				if a > s:
					bits[n][s] = bits[n - 1][s]
				else:
					bits[n][s] = bits[n - 1][s] or bits[n - 1][s - a]
		diff = sm
		for x in range(sm // 2, -1, -1):
			if bits[N][x]:
				diff = sm - 2 * x
				break
		if sm + diff <= 2 * G:
			possible = True
	if possible:
		print('YES')
	else:
		print('NO')


from math import inf
t = int(input().strip())
for _ in range(t):
	(n, g) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	s = sum(a)
	if s > 2 * g:
		print('NO')
		continue
	if max(a) > g:
		print('NO')
		continue
	table = {}

	def knapsack(i, g):
		if g < 0:
			return -inf
		if g == 0:
			return 0
		if i == 0:
			if g >= a[i]:
				return a[i]
			return 0
		if (i, g) not in table:
			table[i, g] = max(knapsack(i - 1, g), knapsack(i - 1, g - a[i]) + a[i])
		return table[i, g]
	first_row = knapsack(n - 1, g)
	if s - first_row <= g:
		print('YES')
	else:
		print('NO')


def dp(n, c):
	if n == N:
		return 0
	if c == 0:
		return 0
	if results[n][c] != -1:
		return results[n][c]
	if A[n] > c:
		results[n][c] = dp(n + 1, c)
	else:
		results[n][c] = max(A[n] + dp(n + 1, c - A[n]), dp(n + 1, c))
	return results[n][c]
T = int(input())
for t in range(T):
	entrada0 = input().split()
	N = int(entrada0[0])
	G = int(entrada0[1])
	A = [int(x) for x in input().split()]
	results = [[-1 for i in range(G + 1)] for j in range(N + 1)]
	aprox = dp(0, G)
	soma = 0
	for v in A:
		soma = soma + v
	if soma - aprox <= G:
		print('YES')
	else:
		print('NO')


def mochila(i, cr):
	if i == n or cr == 0:
		return 0
	if memo[i][cr] != -1:
		return memo[i][cr]
	if a[i] > cr:
		return mochila(i + 1, cr)
	memo[i][cr] = max(a[i] + mochila(i + 1, cr - a[i]), mochila(i + 1, cr))
	return memo[i][cr]
t = int(input())
for i in range(t):
	(n, g) = map(int, input().split())
	a = list(map(int, input().split()))
	total = 0
	for k in a:
		total += k
	memo = []
	for k in range(n + 1):
		memo.append([-1] * (g + 1))
	time = mochila(0, g)
	if total - time <= g:
		print('YES')
	else:
		print('NO')


def dp(i, rt, time, memo):
	if i == n or rt == 0:
		return 0
	if memo[i][rt] != -1:
		return memo[i][rt]
	if time[i] > rt:
		return dp(i + 1, rt, time, memo)
	enter = time[i] + dp(i + 1, rt - time[i], time, memo)
	dont = dp(i + 1, rt, time, memo)
	memo[i][rt] = enter if enter > dont else dont
	return memo[i][rt]
T = int(input())
for test in range(T):
	(n, g) = map(int, input().split())
	times = list(map(int, input().split()))
	memo = [[-1 for i in range(g + 1)] for j in range(n + 1)]
	t = sum(times)
	x = dp(0, g, times, memo)
	print('YES' if t - x <= g else 'NO')


def maxpack(index, capacity):
	if index >= n or capacity == 0:
		return 0
	if poss[index][capacity] >= 0:
		return poss[index][capacity]
	if a[index] <= capacity:
		poss[index][capacity] = max(a[index] + maxpack(index + 1, capacity - a[index]), maxpack(index + 1, capacity))
	else:
		poss[index][capacity] = maxpack(index + 1, capacity)
	return poss[index][capacity]
t = int(input().strip())
for u in range(t):
	(n, g) = [int(x) for x in input().strip().split(' ')]
	a = [int(x) for x in input().strip().split(' ')]
	size = sum(a)
	if size <= g:
		print('YES')
		continue
	if size > 2 * g:
		print('NO')
		continue
	poss = [[-1 for _ in range(g + 1)] for y in range(n)]
	onerow = maxpack(0, g)
	if size - onerow <= g:
		print('YES')
	else:
		print('NO')


from itertools import combinations

def main():
	for t in range(int(input())):
		(n, g) = map(int, input().strip().split())
		a = list(map(int, input().strip().split()))
		a.sort(reverse=True)
		result = job(g, a)
		print(result)

def job(g, a):
	if max(a) > g:
		return 'NO'
	asum = 0
	al = []
	bsum = 0
	bl = []
	for (i, num) in enumerate(a):
		if asum > bsum:
			bsum += num
			bl.append(num)
		else:
			asum += num
			al.append(num)
	if asum > g and bsum > g:
		return 'NO'
	elif asum > g or bsum > g:
		if bsum > asum:
			(asum, bsum) = (bsum, asum)
			(al, bl) = (bl, al)
		ad = asum - g
		bd = g - bsum
		for x in al:
			for y in (yd for yd in bl if x > yd):
				if ad <= x - y <= bd:
					return 'YES'
		return 'NO'
	else:
		return 'YES'
main()


def f(A, i, s0, s, memo):
	if i == len(A):
		return max(s0, s - s0)
	ans = memo[i][s0]
	if ans < 0:
		ans = min(f(A, i + 1, s0 + A[i], s, memo), f(A, i + 1, s0, s, memo))
		memo[i][s0] = ans
	return ans

def solve(A):
	s = sum(A)
	memo = [[-1] * 10000 for _ in range(len(A))]
	return f(A, 0, 0, s, memo)
for I in range(int(input())):
	(N, G) = map(int, input().split())
	A = [int(x) for x in input().split()]
	print('YES' if solve(A) <= G else 'NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


import math
import itertools

def is_possible(A, G):
	states = {0}
	for i in A:
		additionnal = set()
		for x in states:
			if i + x > G:
				break
			else:
				additionnal.add(x + i)
		states |= additionnal
	if sum(A) - max(states) <= G:
		return True
	else:
		return False
for _ in range(int(input())):
	(N, G) = (int(e) for e in input().split())
	A = [int(e) for e in input().split()]
	print('YES' if is_possible(A, G) else 'NO')


def isPossible(A, N, G):
	if max(A) > G:
		return 'NO'
	total = sum(A)
	if total <= G:
		return 'YES'
	if total > 2 * G:
		return 'NO'
	S1 = findMin(A, N, total)
	return 'YES' if max(total - S1, S1) <= G else 'NO'

def findMin(arr, N, total):
	row = [False] * (total + 1)
	dp = [row.copy() for i in range(N + 1)]
	for i in range(N + 1):
		dp[i][0] = True
	for i in range(1, N + 1):
		for j in range(1, total + 1):
			dp[i][j] = dp[i - 1][j]
			if arr[i - 1] <= j:
				dp[i][j] |= dp[i - 1][j - arr[i - 1]]
	j = int(total / 2)
	while j >= 0:
		if dp[N][j] == True:
			return j
		j -= 1

def minPartition(arr, i, S1, S2, cache):
	if i < 0:
		return (S1, S2)
	if (i, S1) not in cache:
		inc = minPartition(arr, i - 1, S1 + arr[i], S2, cache)
		exc = minPartition(arr, i - 1, S1, S2 + arr[i], cache)
		cache[i, S1] = inc if abs(inc[0] - inc[1]) < abs(exc[0] - exc[1]) else exc
	return cache[i, S1]
T = int(input().strip())
for a0 in range(T):
	(N, G) = [int(s) for s in input().strip().split(' ')]
	A = [int(s) for s in input().strip().split(' ')]
	print(isPossible(A, N, G))


import sys
t = int(input().strip())
for _ in range(t):
	[n, g] = list(map(int, input().strip().split(' ')))
	l = list(map(int, input().strip().split(' ')))
	s = sum(l)
	mean = s // 2
	flag = 0
	if s > 2 * g:
		print('NO')
		continue
	sums = set([0])
	for elem in l:
		aux = set([i + elem for i in sums])
		if any((e >= mean and e <= g for e in aux)):
			print('YES')
			flag = 1
			break
		sums.update([a for a in aux if a < g])
	if not flag:
		print('NO')


import sys

def is_solution_exist(g, array):
	length = len(array)
	g = min(20000, g)
	table = []
	for index in range(length + 1):
		table.append([0] * (g + 1))
	for x in range(1, length + 1):
		time = array[x - 1]
		for y in range(g + 1):
			if time <= y:
				table[x][y] = max(table[x - 1][y], table[x - 1][y - time] + time)
			else:
				table[x][y] = table[x - 1][y]
	time_summary_value = sum(array)
	if time_summary_value - table[length][g] > g:
		return 'NO'
	else:
		return 'YES'
test_case = int(input().strip())
for i in range(test_case):
	(n, g) = list(map(int, input().strip().split()))
	array = list(map(int, input().strip().split()))
	print(is_solution_exist(g, array))


def indian_job(G, A):
	s = sum(A)
	if G < s / 2:
		return False
	dp = [[]] * (len(range(G)) + 1)
	for i in range(G + 1):
		dp[i] = [False] * len(A)
	dp[0] = [True] * len(A)
	for i in range(1, G + 1):
		for j in range(len(A)):
			if i == A[j]:
				dp[i][j] = True
				continue
			if j > 0:
				dp[i][j] = dp[i][j - 1]
				if not dp[i][j]:
					if i > A[j]:
						dp[i][j] = dp[i - A[j]][j - 1]
	if dp[G][-1]:
		return True
	for g in range(G - 1, -1, -1):
		if dp[g][-1]:
			if s - g <= G:
				return True
	return False
q = int(input().strip())
for i in range(q):
	(N, G) = list(map(int, input().strip().split(' ')))
	A = list(map(int, input().strip().split(' ')))
	ret = indian_job(G, A)
	if ret:
		print('YES')
	else:
		print('NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


import os
import sys

def indianJob(g, arr):
	YES_MSG = 'YES'
	NO_MSG = 'NO'
	arr_sum = sum(arr)
	if 2 * g < arr_sum:
		return NO_MSG
	n = len(arr)
	table = [[-1 for j in range(n + 1)] for i in range(g + 1)]
	for j in range(n + 1):
		table[0][j] = True
	for i in range(g):
		table[i + 1][0] = False
	for i in range(1, g + 1):
		for j in range(1, n + 1):
			if i - arr[j - 1] >= 0:
				table[i][j] = table[i][j - 1] or table[i - arr[j - 1]][j - 1]
			else:
				table[i][j] = table[i][j - 1]
	if table[-1][-1]:
		return YES_MSG
	else:
		for i in range(g, -1, -1):
			if table[i][n]:
				last_sum = i
				break
		if arr_sum - last_sum <= g:
			return YES_MSG
		return NO_MSG
t = int(input())
for t_itr in range(t):
	ng = input().split()
	n = int(ng[0])
	g = int(ng[1])
	arr = list(map(int, input().rstrip().split()))
	result = indianJob(g, arr)
	print(result)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


T = int(input())
for t in range(T):
	(N, G) = map(int, input().split())
	A = [int(x) for x in input().split()]
	s = set([0])
	for x in A:
		for t in list(s):
			s.add(x + t)
	x = sum(A)
	for t in s:
		if t <= G and x - t <= G:
			print('YES')
			break
	else:
		print('NO')


import os
import sys

def indianJob(g, arr):
	Total = sum(arr)
	Possible = [True] + [False] * Total
	for x in arr:
		for i in range(Total, -1, -1):
			if Possible[i]:
				Possible[i + x] = True
	for i in range((Total + 1) // 2, min(Total, g) + 1):
		if Possible[i]:
			print('YES')
			break
	else:
		print('NO')
t = int(input())
for t_itr in range(t):
	ng = input().split()
	n = int(ng[0])
	g = int(ng[1])
	arr = list(map(int, input().rstrip().split()))
	indianJob(g, arr)


def indianJob(g, arr):
	S = sum(arr)
	if S <= g:
		return 'YES'
	if 2 * g < S:
		return 'NO'
	frontier = [(arr[0], 0)]
	for i in range(1, len(arr)):
		if frontier == []:
			return 'NO'
		new_frontier = []
		used = {}
		for f in frontier:
			t1 = f[0] + arr[i]
			t2 = f[1]
			temp1 = (min(t1, t2), max(t1, t2))
			t1 = f[0]
			t2 = f[1] + arr[i]
			temp2 = (min(t1, t2), max(t1, t2))
			if temp1[1] >= S / 2 and temp1[1] <= g or (temp2[1] >= S / 2 and temp2[1] <= g):
				return 'YES'
			if temp1[1] <= g and (not temp1 in used):
				new_frontier.append(temp1)
				used[temp1] = True
			if temp2[1] <= g and (not temp2 in used):
				new_frontier.append(temp2)
				used[temp2] = True
		frontier = new_frontier
	return 'NO'
t = int(input())
for t_itr in range(t):
	ng = input().split()
	n = int(ng[0])
	g = int(ng[1])
	arr = list(map(int, input().rstrip().split()))
	result = indianJob(g, arr)
	print(result)


for _ in range(int(input())):
	(n, g) = map(int, input().split())
	r = list(map(int, input().split()))
	s = set()
	if max(r) > g or sum(r) > g + g:
		print('NO')
		continue
	for t in r:
		if t > g:
			continue
		x = set()
		for a in s:
			if a + t <= g:
				x.add(a + t)
		s.add(t)
		s = s.union(x)
	if sum(r) - max(s) <= g:
		print('YES')
	else:
		print('NO')


import os
import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


def indianJob(g, a):
	s = sum(a)
	dp = [0] * (g + 1)
	for i in a:
		for j in range(g, -1, -1):
			if j >= i:
				dp[j] = max(dp[j], i + dp[j - i])
	t = s // 2 + 1 if s % 2 else s // 2
	return 'YES' if dp[g] >= t else 'NO'
t = int(input())
for t_itr in range(t):
	ng = input().split()
	n = int(ng[0])
	g = int(ng[1])
	arr = list(map(int, input().rstrip().split()))
	print(indianJob(g, arr))


import os
import sys
for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


import os
import sys
for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


def solution(data, g, g0, f):
	for x in data:
		for i in range(g0 - 1, -1, -1):
			if f[i] == 0:
				continue
			ix = i + x
			if ix > g:
				continue
			if ix <= g and ix >= g0:
				return 'YES'
			f[ix] = 1
	return 'NO'
for _ in range(int(input())):
	(n, g) = map(int, input().split(' '))
	(data, c) = ([int(x) for x in input().split(' ')], [0] * 2)
	data.sort(reverse=True)
	if data[0] > g:
		print('NO')
		continue
	for x in data:
		c[c[0] > c[1]] += x
	if max(c) <= g:
		print('YES')
	elif c[0] + c[1] > g + g:
		print('NO')
	else:
		g0 = c[0] + c[1] - g
		f = [0] * (g + 1)
		f[0] = 1
		if c[-1] >= g0 and c[-1] <= g:
			print('YES')
		else:
			print(solution(data, g, g0, f))


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


import heapq
for test in range(int(input())):
	(n, g) = map(int, input().split())
	data = [-int(v) for v in input().split()]
	time = sum(data)
	heapq.heapify(data)
	for i in range(n - 1):
		heapq.heappush(data, -abs(heapq.heappop(data) - heapq.heappop(data)))
	print('NO' if time + data[0] < -2 * g else 'YES')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


import os
import sys
for case in range(int(input())):
	(n, g) = map(int, input().split())
	ls = list(map(int, input().split()))
	t = sum(ls)
	p = [True] + [False] * t
	for x in ls:
		for i in range(t, -1, -1):
			if p[i]:
				p[i + x] = True
	for i in range((t + 1) // 2, min(t, g) + 1):
		if p[i]:
			print('YES')
			break
	else:
		print('NO')


import os
import sys

def indianJob(g, arr):
	for case in range(int(input())):
		(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
		break
	else:
		print('NO')
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')


for case in range(int(input())):
	(N, G) = map(int, input().split())
	A = list(map(int, input().split()))
	total = sum(A)
	possible = [True] + [False] * total
	for x in A:
		for i in range(total, -1, -1):
			if possible[i]:
				possible[i + x] = True
	for i in range((total + 1) // 2, min(total, G) + 1):
		if possible[i]:
			print('YES')
			break
	else:
		print('NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, G) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	if sum(A) > 2 * G:
		print('NO')
	else:
		DP = [[0] * (G + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for w in range(G + 1):
				if i == 0 or w == 0:
					DP[i][w] = 0
				elif A[i - 1] > w:
					DP[i][w] = DP[i - 1][w]
				else:
					DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1])
		print('YES' if sum(A) - DP[N][G] <= G else 'NO')