给定一个整数数组 $$$l_1、l_2、\dots、l_n$$$ 和一个整数 $$$d$$$。是否可以构建满足以下三个条件的树?
- 树包含 $$$n + 1$$$ 个节点。
- 第 $$$i$$$ 条边的长度等于 $$$l_i$$$。
- 树的(加权)直径等于 $$$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$$$。
输出
对于每个测试用例,如果可以构建满足所有条件的树,则输出 $$$\texttt{Yes}$$$,否则输出 $$$\texttt{No}$$$。
您可以以任何大小写(大写或小写)打印字母。
示例
输入 #1
3 4 10 1 2 3 4 4 7 1 4 3 4 6 18 2 4 3 7 6 7
输出 #1
Yes No Yes
注意
下面为您提供了第一个和第三个测试用例的树的插图。其中一个直径通过将其边缘涂成红色来突出显示。