310796: CF1889B. Doremy's Connecting Plan

B. Doremy's Connecting Plantime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Doremy lives in a country consisting of $n$ cities numbered from $1$ to $n$, with $a_i$ people living in the $i$-th city. It can be modeled as an undirected graph with $n$ nodes.

Initially, there are no edges in the graph. Now Doremy wants to make the graph connected.

To do this, she can add an edge between $i$ and $j$ if

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

where $S$ is the set of all the nodes that are currently in the same connected component of either $i$ or $j$, and $c$ is a given constant.

Can Doremy make the graph connected?

Two nodes $(i, j)$ are in the same connected component if there exists a path from $i$ to $j$. A graph is connected if all its nodes are in the same connected component.

Input

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line contains two integers $n$, $c$ ($2\le n\le 2\cdot 10^5$, $1 \le c \le 10^6$) — the number of nodes and the constant.

The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ($0 \le a_i \le 10^{12}$) — the number of people living in the $i$-th city.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, print "YES" (without quotes), if it is possible to make the graph connected, and "NO" (without quotes) otherwise.

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

ExampleInput

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

Output

Yes
Yes
Yes
No
No
Yes
No

Note

In the first test case, Doremy can add edges in the following order:

1. Add $(1,2)$. This operation is valid because $a_1 + a_2 = 20 \ge i\cdot j \cdot c = 20$.
2. Add $(1,3)$. This operation is valid because $a_1 + a_2 + a_3 = 35 \ge i \cdot j \cdot c = 30$.
3. Add $(1,4)$. This operation is valid because $a_1 + a_2 + a_3 + a_4 = 45 \ge i \cdot j \cdot c = 40$.

In the second test case, Doremy can add edge $(1,2)$ because $a_1 + a_2 =2 \ge 1 \cdot 2 \cdot 1$. After that, the graph is connected.

In the third test case, Doremy can add edges in the order $(5,4)$, $(5,3)$, $(5,2)$ and $(5,1)$.

In the fourth test case, Doremy cannot add any edge at all.

**题目大意：**

多雷米居住在一个由 $ n $ 个城市组成的国家，城市编号从 $ 1 $ 到 $ n $，第 $ i $ 个城市居住着 $ a_i $ 人。这个国家可以被视为一个具有 $ n $ 个节点的无向图。

最初，图中没有边。现在多雷米想要使得这个图变得**连通**。为了做到这一点，如果集合 $ S $ 中所有节点的 $ a_k $ 之和满足不等式 $ \sum_{k \in S} a_k \ge i \cdot j \cdot c $，她可以在 $ i $ 和 $ j $ 之间添加一条边，其中 $ 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
```**题目大意：** 多雷米居住在一个由 $ n $ 个城市组成的国家，城市编号从 $ 1 $ 到 $ n $，第 $ i $ 个城市居住着 $ a_i $ 人。这个国家可以被视为一个具有 $ n $ 个节点的无向图。 最初，图中没有边。现在多雷米想要使得这个图变得**连通**。为了做到这一点，如果集合 $ S $ 中所有节点的 $ a_k $ 之和满足不等式 $ \sum_{k \in S} a_k \ge i \cdot j \cdot c $，她可以在 $ i $ 和 $ j $ 之间添加一条边，其中 $ 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 ```