F. Постройте дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$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}$$$ в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
3
4 10
1 2 3 4
4 7
1 4 3 4
6 18
2 4 3 7 6 7
Выходные данные
Yes
No
Yes
Примечание

Ниже приведены иллюстрации деревьев для первого и третьего наборов входных данных. Один из диаметров выделен путем окрашивания его ребер в красный цвет.