310805: CF1890D. Doremy's Connecting Plan

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

**Doremy的连接计划**

**题目大意：**
Doremy生活在一个由n个城市组成的国家中，城市编号从1到n，第i个城市有a_i个人居住。这个国家可以建模为一个有n个节点的无向图。

最初，图中没有边。现在Doremy想要使得这个图变成**连通图**。为了做到这一点，如果满足以下条件，她可以在i和j之间添加一条边：

\[
\sum_{k \in S} a_k \ge i \times j \times c
\]

其中S是当前与i或j在同一连通分量中的所有节点的集合，c是一个给定的常数。

问Doremy能否使这个图变成连通图。

如果存在一条从i到j的路径，那么节点(i, j)在同一连通分量中。当一个图的所有节点都在同一连通分量中时，该图是连通的。

**输入数据格式：**
输入包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数n、c（2≤n≤2×10^5，1≤c≤10^6）——节点的数量和常数。

每个测试用例的第二行包含n个整数a_1,a_2,…,a_n（0≤a_i≤10^12）——第i个城市的居民数量。

保证所有测试用例的n之和不超过2×10^5。

**输出数据格式：**
对于每个测试用例，如果可能使图变成连通图，则输出:YES”（不包含引号），否则输出“No”（不包含引号）。

字母可以以任何大小写形式打印。**Doremy的连接计划** **题目大意：** Doremy生活在一个由n个城市组成的国家中，城市编号从1到n，第i个城市有a_i个人居住。这个国家可以建模为一个有n个节点的无向图。 最初，图中没有边。现在Doremy想要使得这个图变成**连通图**。为了做到这一点，如果满足以下条件，她可以在i和j之间添加一条边： \[ \sum_{k \in S} a_k \ge i \times j \times c \] 其中S是当前与i或j在同一连通分量中的所有节点的集合，c是一个给定的常数。 问Doremy能否使这个图变成连通图。 如果存在一条从i到j的路径，那么节点(i, j)在同一连通分量中。当一个图的所有节点都在同一连通分量中时，该图是连通的。 **输入数据格式：** 输入包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数n、c（2≤n≤2×10^5，1≤c≤10^6）——节点的数量和常数。 每个测试用例的第二行包含n个整数a_1,a_2,…,a_n（0≤a_i≤10^12）——第i个城市的居民数量。 保证所有测试用例的n之和不超过2×10^5。 **输出数据格式：** 对于每个测试用例，如果可能使图变成连通图，则输出:YES”（不包含引号），否则输出“No”（不包含引号）。 字母可以以任何大小写形式打印。