amazing-test

Akshara is a Maths teacher at Dynamic Public School.One day she decided to take an unusual test of all her students.She took all her students to a fair.There she took them to a candy room.The room had 2 doors and behind each door was unlimited supply of candies.The excitement of the students could not be measured.Each student wanted a specific amount of candies.Now here was the test.

At a time 1 student could enter 1 door.After he exits another will enter.No time is lost when there is change of students.For proccessing 1 candy it took 1 second.The teacher gave exactly X amount of time for all the students
to get their specific amount of candies.So the students ask you for help in determining whether it is possible for all the students to get their candies or not  in X amount of time.

Input:

The first line contains T denoting the number of test cases.Each testcase consist of two lines containing n and x denoting the number of students and the time given by the teacher.The next line contains n space separated numbers denoting the amount of candy each student wants.

Output:

For each testcase print YES if it is possible or NO.

Constraints:

1 ≤ T ≤ 25

1 ≤ N ≤ 100

1 ≤ x ≤ 100000

0 ≤ A[i] ≤ 100

SAMPLE INPUT
2
3 4
2 4 2
3 3
3 3 3


SAMPLE OUTPUT
YES
NO

Explanation

In the first testcase:

At t=0 Student 3 enters door 1 and student 2 enters door 2.

At t=2 Student 1 enters door 1 and student 3 exits.

At t=4 Student 2 and 1 exits.

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
t = int(input())
import random
for ti in range(t):
	n,x = list(map(int,input().split()))
	a = [0 for _ in range(n)]
	a = list(map(int,input().split()))
	#a = sorted(a,reverse = True)
	for p in range(1000):
		t1,t2 = 0, 0
		aa = random.sample(a,n)
		i = 0
		ok = True
		while i<n:
			if t1<t2:
				t1 += aa[i]
			else:
				t2 += aa[i]
			i += 1
			if max(t1,t2)>x:
				ok = False
				break
		if ok:
			print("YES")
			break
	if not ok:
		print("NO")
		


# http://www.hackerearth.com/webengage-hiring-challenge-1/algorithm/amazing-test/


from sys import stdin


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


def solve():
	n, x = getInt()
	A = getInt()
	A.sort()
	s = sum(A)
	W = [False] * (s + 1)
	W[0] = True
	for e in A:
		for w in range(s, e - 1, -1):
			W[w] = W[w] or W[w - e]
	ret = 100000000
	# print W
	for i, w in enumerate(W):
		if w:
			ret = min(ret, max(i, s - i))
	if ret <= x:
		print("YES")
	else:
		print("NO")


if __name__ == '__main__':
	t, = getInt()
	for _ in range(t):
		solve()