题目描述

$i666$有一张纸带，上面有$n$个排成一行的单元格，他决定空白的纸袋太单调了，于是想给这些单元格涂上$m$种颜色。出于某种没学考虑，他认为第$i$种颜色必须准确使用$a_i$次，而且每$k$个连续的单元格，它们的颜色必须是不同的。

请帮助$i666$找出是否有这样的方法来绘制单元格。

输入格式

第一行包含一个整数$t$ $(1 \le t \le 10000)$，表示测试用例的数量。

每一个测试用例的第一行包含三个整数$n$,$m$,$k$ $(1 \le k \le n \le 10^9 、1 \le m \le 10^5 , m \le n)$,其中$n$表示单元格的个数，$m$表示颜色的个数，$k$表示每$k$个连续的单元格的颜色必须是不同的。

每个测试用例的第二行包含$m$个整数 $a_1, a_2, \cdots , a_m$$(1 \le a_i \le n)$表示颜色的使用个数，保证$a_1 + a_2 + \ldots + a_m = n$

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

输出格式

对于每个测试用例，如果至少有一种可能的染色方案，输入"YES",否则输出"NO"。

样例

intput

2
12 6 2
1 1 1 1 1 7
12 6 2
2 2 2 2 2 2

output

NO
YES

提示

在第一个测试用例中，无法给满足所有条件的单元格着色。

在第二个测试案例中，我们可以对单元格着色如下：$(1，2，1，2，3，4，3，4，5，6，5，6)$2 个连续的单元格，它们的颜色是不同的。