310988: CF1917F. Construct Tree

F. Construct Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$.

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).

ExampleInput

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

Output

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.

题目大意：给定一个整数数组 $ l_1, l_2, \dots, l_n $ 和一个整数 $ d $，判断是否可以构造一棵满足以下三个条件的树：

1. 树包含 $ n + 1 $ 个节点。
2. 第 $ i $ 条边的长度等于 $ l_i $。
3. 树的（加权）直径等于 $ d $。

输入数据格式：每个测试包含多个测试用例。第一行包含一个整数 $ t $ ($ 1 \leq t \leq 250 $) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $ n $, $ d $ ($ 2 \leq n \leq 2000, 1 \leq d \leq 2000 $)。

每个测试用例的第二行包含 $ n $ 个整数 $ l_1, l_2, \dots, l_n $ ($ 1 \leq l_i \leq d $)。

保证所有测试用例的 $ n $ 之和不超过 $ 2000 $。

输出数据格式：对于每个测试用例，如果可以构造一棵满足所有条件的树，则输出 `Yes`，否则输出 `No`。

字母大小写不限。题目大意：给定一个整数数组 $ l_1, l_2, \dots, l_n $ 和一个整数 $ d $，判断是否可以构造一棵满足以下三个条件的树： 1. 树包含 $ n + 1 $ 个节点。 2. 第 $ i $ 条边的长度等于 $ l_i $。 3. 树的（加权）直径等于 $ d $。 输入数据格式：每个测试包含多个测试用例。第一行包含一个整数 $ t $ ($ 1 \leq t \leq 250 $) —— 测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数 $ n $, $ d $ ($ 2 \leq n \leq 2000, 1 \leq d \leq 2000 $)。 每个测试用例的第二行包含 $ n $ 个整数 $ l_1, l_2, \dots, l_n $ ($ 1 \leq l_i \leq d $)。 保证所有测试用例的 $ n $ 之和不超过 $ 2000 $。 输出数据格式：对于每个测试用例，如果可以构造一棵满足所有条件的树，则输出 `Yes`，否则输出 `No`。 字母大小写不限。