- Prepare
- Algorithms
- Dynamic Programming
- The Indian Job

# 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 *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.