Tug of War

Interview

Time limit1sMemory limit128 MB

Summary

Decide whether N student weights (4 to 30) split into two teams whose total strengths differ by at most X.

Level: Medium5 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

The computer science department of Pilseung University is preparing its autumn sports day. The last event is tug of war. To keep the department together and make the match fun, the students are split so that the two opposing teams are as evenly matched as possible. The strength of a team is the sum of the weights of the students on it.

Write a program that decides whether the $N$ students can be split into two teams whose strengths differ by at most $X$ . The two teams do not have to have the same number of students.

Input

Input arrives on standard input. The first line holds the number of test cases $T$ ( $1 \le T \le 10$ ).

Each test case takes three lines. The first line has the number of students $N$ ( $4 \le N \le 30$ ), the second line has an integer $X$ ( $X \ge 0$ ), and the third line has the weights of the $N$ students, separated by spaces. Every weight is an integer between $40$ and $160$ .

Output

Write the answers to standard output. For each test case, print YES if the $N$ students can be split into two teams whose strengths differ by at most $X$ , and NO if they cannot. Print one answer per line.

Examples1

Example 1

Input

3
4
10
51 74 52 73
6
5
58 69 44 59 70 47
5
10
78 127 131 49 81

Expected output

YES
YES
NO