Cirno_9baka 有一条纸带,上面有一排 $$$n$$$ 个单元格。由于他认为空白纸带太暗淡,他想给这些单元格涂上$$$m$$$种颜色。出于某些美学原因,他认为第 $$$i$$$ 颜色必须恰好使用 $$$a_i$$$ 次,并且对于每个 $$$k$$$ 连续单元格,它们的颜色必须不同。
帮助 Cirno_9baka 弄清楚是否有这样的方法来绘制单元格。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,如果至少有一种可能的着色方案,则输出“YES”;否则,输出“NO”。
您可以在任何情况下打印每个字母(例如,“YES”、“Yes”、“yes”和“yEs”都将被识别为肯定答案)。
示例
输入 #1
2 12 6 2 1 1 1 1 1 7 12 6 2 2 2 2 2 2 2
输出 #1
NO YES
注意
在第一个测试用例中,无法对满足所有条件的单元格进行着色。
在第二个测试用例中,我们可以按如下方式为单元格着色:$$$(1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6)$$$。对于任何 $$$2$$$ 连续单元格,它们的颜色是不同的。