B. План подключения от Дореми
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дореми живёт в стране, состоящей из $$$n$$$ городов, пронумерованных от $$$1$$$ до $$$n$$$, причём в $$$i$$$-м городе живёт $$$a_i$$$ человек. Страну можно смоделировать в виде неориентированного графа с $$$n$$$ вершинами.

Изначально в графе нет рёбер. Дореми хочет сделать граф связным.

Для этого она может добавить ребро между $$$i$$$ и $$$j$$$, если

$$$$$$ \sum_{k \in S} a_k \ge i\cdot j \cdot c, $$$$$$

где $$$S$$$ — множество всех вершин, которые в данный момент находятся в одной компоненте связности либо с $$$i$$$ или с $$$j$$$, а $$$c$$$ — фиксированная константа.

Может ли Дореми сделать граф связным?

Две вершины $$$(i, j)$$$ находятся в одной компоненте связности, если существует путь из $$$i$$$ в $$$j$$$. Граф является связным, если все его вершины находятся в одной компоненте связности.

Входные данные

Входные данные состоят из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит два целых числа $$$n$$$, $$$c$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$1 \le c \le 10^6$$$) — количество вершин и константу.

Вторая строка каждого набора входных данных содержит $$$ n $$$ целых чисел $$$ a_1,a_2,\ldots,a_n $$$ ($$$0 \le a_i \le 10^{12}$$$) — количество людей, проживающих в $$$i$$$-м городе.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES» (без кавычек), если возможно сделать граф связным, и «NO» (без кавычек) в противном случае.

Буквы можно выводить в любом регистре (верхнем или нижнем).

Пример
Входные данные
7
4 10
0 20 15 10
2 1
1 1
5 1
0 1 0 4 199
5 2
1 1 3 1 1
5 5
5 6 1 10 2
5 1000000
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
3 1
0 0 2
Выходные данные
Yes
Yes
Yes
No
No
Yes
No
Примечание

В первом наборе входных данных Дореми может добавлять ребра в следующем порядке:

  1. Добавить $$$(1,2)$$$. Эта операция допустима, так как $$$a_1 + a_2 = 20 \ge i\cdot j \cdot c = 20$$$.
  2. Добавить $$$(1,3)$$$. Эта операция допустима, так как $$$a_1 + a_2 + a_3 = 35 \ge i \cdot j \cdot c = 30$$$.
  3. Добавить $$$(1,4)$$$. Эта операция допустима, так как $$$a_1 + a_2 + a_3 + a_4 = 45 \ge i \cdot j \cdot c = 40$$$.

Во втором наборе входных данных Дореми может добавить ребро $$$(1,2)$$$, так как $$$a_1 + a_2 =2 \ge 1 \cdot 2 \cdot 1$$$. После этого граф становится связным.

В третьем наборе входных данных Дореми может добавлять ребра в порядке $$$(5,4)$$$, $$$(5,3)$$$, $$$(5,2)$$$ и $$$(5,1)$$$.

В четвертом наборе входных данных Дореми вообще не может добавить ни одного ребра.