DOTAA - DOTA HEROES

Defence Of The Ancients (DOTA) is one of the most addictive online multiplayer games. There are n heroes in our team and our motto is to conquer the opponent’s empire. To safeguard their empire, the opponents had constructed m towers on the path. If one or more heroes get into the sight of a tower, then the tower does D amount of damage to one of those heroes at that instant (i.e. one of the heroes’ health decreases by D). Any hero will die if his health H <= 0. Once a tower attacks one of the heroes, all the heroes in the sight of that tower at that instant get out of its sight. Find whether all of the heroes in our team can reach the opponent’s empire alive.

Input

The first line consists of one integer t representing the number of test cases. For each test case, the first line consists of three integers n, m and D, the number of heroes, number of towers and the amount of Damage respectively. The next n lines consist of an integer representing the health of respective hero.

Output

Just a word “YES” if we can reach the opponent’s empire alive, else “NO”.

Constraints

1 <= t <= 500
1 <= n <= 500
1 <= m <= n
1 <= D, H <= 20000

Example

Input:
3
6 3 400
500
500
500
500
500
500
6 5 400
800
800
801
200
200
200
6 3 400
401
401
400
200
400
200

Output:
YES
NO
NO

Explanation of test case 1:

One of the possible solutions is: First, three of the heroes can goes together. One of them receives 400 damage from the first tower and all of them cross it. Then while crossing the next tower, one of the heroes who is at 500 health gets 400 damage and all of them cross it. Then the third hero receives the damage when crossing the last tower. Similarly the other 3 heroes can reach the opponent’s base together without dying.


Added by:cegprakash
Date:2011-12-25
Time limit:0.208s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF

hide comments
2014-03-13 19:22:01 VARUN KUMARE
Hey guys! u may also try it!
i/p:
6 9 400
601
601
601
601
601
601
6 9 400
801
801
801
801
801
801
6 3 400
500
500
200
500
500
500
o/p:
NO
YES
YES

Last edit: 2013-01-05 23:59:55
2014-03-13 19:22:01 Hitman
WA

Last edit: 2013-01-02 13:48:36
2014-03-13 19:22:01 prad@tt
thank u D...now i got it
2014-03-13 19:22:01 ram chandra uppadhay
what would be the answer of test case given by ashish kumar yogi
2014-03-13 19:22:01 Dota_lover *_*
i m addicted to this game :D
2014-03-13 19:22:01 :)
hmm..good ques .
could have been made more interesting
2014-03-13 19:22:01 Simón Murillo Gómez
Easy one
O(n^2) can pass.
2014-03-13 19:22:01 Neeraj Bhat
@ashish kumar yogi:- thnx. got AC only reading ur comment...

Last edit: 2012-07-07 10:30:20
2014-03-13 19:22:01 ashish kumar yogi
take an example.. let there are 3 towers.. having D=400 each... and there are 6 soldiers... having capacity as--{1201,200,200,200,200,200}...now can any1 tell me that a single man can bear all the attacks of tower or all tower cannot attack only one person during the war ??
2014-03-13 19:22:01 :D
YES
YES

But those are really trivial cases. I don't really see what problems could you have with those.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.