Coloring
Contest: Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1500
Tags: constructive algorithms, greedy, math

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.

Input format:
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$$$.

Output format:
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).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
2
12 6 2
1 1 1 1 1 7
12 6 2
2 2 2 2 2 2

Example output:
NO
YES

Editorial:
First, We can divide $$$n$$$ cells into $$$\left\lceil\frac{n}{k}\right\rceil$$$ segments that except the last segment, all segments have length $$$k$$$. Then in each segment, the colors in it are pairwise different. It's easy to find any $$$a_i$$$ should be smaller than or equal to $$$\left\lceil\frac{n}{k}\right\rceil$$$.
Then we can count the number of $$$a_i$$$ which is equal to $$$\left\lceil\frac{n}{k}\right\rceil$$$. This number must be smaller than or equal to $$$n \bmod k$$$, which is the length of the last segment.
All $$$a$$$ that satisfies the conditions above is valid. We can construct a coloring using the method below:
First, we pick out all colors $$$i$$$ that $$$a_i=\left\lceil\frac{n}{k}\right\rceil$$$, then we use color $$$i$$$ to color the $$$j$$$-th cell in each segment.
Then we pick out all colors $$$i$$$ that $$$a_i<\left\lceil\frac{n}{k}\right\rceil-1$$$ and use these colors to color the rest cells with cyclic order(i.e. color j-th cell of the first segment, of second the segment ... of the $$$\left\lceil\frac{n}{k}\right\rceil$$$ segment, and let $$$j++$$$. when one color is used up, we begin to use the next color)
At last, we pick out all colors $$$i$$$ that $$$a_i=\left\lceil\frac{n}{k}\right\rceil-1$$$, and color them with the cyclic order.
This method will always give a valid construction.