We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Indian Job

The Indian Job

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 ith 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 ith robber needs to be in the vault.

Constraints

1 <= T <= 20
1 <= N <= 100
0 <= G <= 1000000 (106)
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.