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

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

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