codeforces#P1917F. Construct Tree

    ID: 34329 远端评测题 2000ms 256MiB 尝试: 6 已通过: 1 难度: 9 上传者: 标签>bitmasksconstructive algorithmsdptrees*2500

Construct Tree

Description

You are given an array of integers $l_1, l_2, \dots, l_n$ and an integer $d$. Is it possible to construct a tree satisfying the following three conditions?

  • The tree contains $n + 1$ nodes.
  • The length of the $i$-th edge is equal to $l_i$.
  • The (weighted) diameter of the tree is equal to $d$.

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 250$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$, $d$ ($2 \leq n \leq 2000, 1 \leq d \leq 2000$).

The second line of each test case contains $n$ integers $l_1, l_2, \dots, l_n$ ($1 \leq l_i \leq d$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

For each test case, output $\texttt{Yes}$ if it is possible to construct a tree that satisfies all the conditions, and $\texttt{No}$ otherwise.

You can print the letters in any case (upper or lower).

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 250$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$, $d$ ($2 \leq n \leq 2000, 1 \leq d \leq 2000$).

The second line of each test case contains $n$ integers $l_1, l_2, \dots, l_n$ ($1 \leq l_i \leq d$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

Output

For each test case, output $\texttt{Yes}$ if it is possible to construct a tree that satisfies all the conditions, and $\texttt{No}$ otherwise.

You can print the letters in any case (upper or lower).

3
4 10
1 2 3 4
4 7
1 4 3 4
6 18
2 4 3 7 6 7
Yes
No
Yes

Note

Below, you are given the illustrations of trees for the first and third test cases. One of the diameters is highlighted by coloring its edges in red.