CF1774B.Coloring

Cirno_9baka has a paper tape with $n$ cells in a row on it. As he thinks that the blank paper tape is too dull, he wants to paint these cells with $m$ kinds of colors. For some aesthetic reasons, he thinks that the $i$-th color must be used exactly $a_i$ times, and for every $k$ consecutive cells, their colors have to be distinct.

Help Cirno_9baka to figure out if there is such a way to paint the cells.

Cirno_9baka 有一条由 $n$ 个格子排成一行的纸带。由于他认为空白纸带过于单调，他打算用 $m$ 种颜色来涂染这些格子。出于某些美学原因，他认为第 $i$ 种颜色必须恰好使用 $a_i$ 次，并且任意连续 $k$ 个格子的颜色都必须互不相同。

请帮助 Cirno_9baka 判断是否存在一种满足上述条件的涂色方案。

The first line contains a single integer $t$ ($1 \leq t \leq 10\,000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains three integers $n$, $m$, $k$ ($1 \leq k \leq n \leq 10^9$, $1 \leq m \leq 10^5$, $m \leq n$). Here $n$ denotes the number of cells, $m$ denotes the number of colors, and $k$ means that for every $k$ consecutive cells, their colors have to be distinct.

The second line of each test case contains $m$ integers $a_1, a_2, \cdots , a_m$ ($1 \leq a_i \leq n$) — the numbers of times that colors have to be used. It's guaranteed that $a_1 + a_2 + \ldots + a_m = n$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10\,000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$、$k$（$1 \leq k \leq n \leq 10^9$，$1 \leq m \leq 10^5$，且 $m \leq n$）。其中，$n$ 表示单元格总数，$m$ 表示颜色种类数，$k$ 表示：任意连续 $k$ 个单元格的颜色必须互不相同。

每个测试用例的第二行包含 $m$ 个整数 $a_1, a_2, \cdots , a_m$（$1 \leq a_i \leq n$），表示每种颜色需使用的次数。保证 $a_1 + a_2 + \ldots + a_m = n$。

保证所有测试用例中 $m$ 的总和不超过 $10^5$。

For each test case, output "YES" if there is at least one possible coloring scheme; otherwise, output "NO".

You may print each letter in any case (for example, "YES", "Yes", "yes", and "yEs" will all be recognized as positive answers).

对于每个测试用例，如果至少存在一种可行的染色方案，则输出 “YES”；否则输出 “NO”。

你可以以任意大小写形式输出每个字母（例如，“YES”、“Yes”、“yes” 和 “yEs” 均会被识别为肯定答案）。

In the first test case, there is no way to color the cells satisfying all the conditions.

In the second test case, we can color the cells as follows: $(1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6)$. For any $2$ consecutive cells, their colors are distinct.

在第一个测试用例中，不存在满足所有条件的染色方案。

在第二个测试用例中，我们可以按如下方式对格子进行染色：$(1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6)$。对于任意两个相邻的格子，它们的颜色均不相同。