Researcher Levi

Time: 2 s
Memory: 125 MB

Levi is organizing a survey for his research project. He has invited people from \( k \) different age groups to participate. The \(i\)-th age group has exactly \(a_i\) people.
Levi has \(n\) rooms available for conducting the survey. To ensure unbiased results, he has set a rule: each room can contain people from multiple age groups, but from any single age group, at most \(x\) people can be placed in the same room.

Levi is quite worried about organizing this survey efficiently and has asked for your help! Your task is to help Levi determine whether it's possible to distribute all people among the \(n\) rooms while satisfying his constraint.

Input

The first line contains a single integer \(t\) the number of test cases. For each test case:
The first line contains three integers \(n, k, \) and \(x\) the number of rooms, the number of age groups, and the maximum number of people from the same age group that can be placed in any single room, respectively.
The second line contains \(k\) integers \(a_1, a_2, ..., a_k \) the number of people in each age group.

Constraint

1 <= t <= 1000
1 <= n <= 100000
1 <= k <= 100
1 <= x, a[i] <= 100000

Output

For each test case, output \(YES\) if it's possible to distribute all people according to the given constraint, and \(NO\) otherwise.

Examples

Input	Output
3 3 2 2 4 5 2 3 1 6 3 4 1 4 3 8 12 15 20	YES NO NO

Notes

In the first test case, we can distribute the people as follows:

Room 1: 2 people from group 1, 2 people from group 2
Room 2: 2 people from group 1, 2 people from group 2
Room 3: 1 person from group 2

Problem ID	508
Time Limit	2000 ms
Memory Limit	128000 KB
Moderators	meheraj_hossain_ , tafsiruzzaman , fahimcp495 , osama_bq , Dr_KeK , sagorahmedmunna , Rakib , refred1 , amirhozaifa , puja_chakraborty , shamima_ananna

You need to Login or Registration for submit your solution