beecrowd | 1884

Fighting the Rajasi

By Stefano Tommasini, Universidade de São Paulo BR Brazil

Timelimit: 1

Muay Thai is a martial art originated in Thailand. Many of its practitioners became legends among Thai people. Among these legendary fighters, Nai Khanom Tom is considered the very best. Here's one of his famous anecdotes.

Burma's king Mangra made Nai Khanom Tom, who was a war prisoner, duel one of the finest Burmese fighters in order to judge their fighting styles. Nai Khanom Tom effortlessly beat his opponent. However, the referee claimed that Nai Khanom Tom only won because he performed Ram Muay, a ritualistic dance move. The king then ordered Nai to duel ten Burmese warriors, one after another. Nai Khanom Tom still beat them all. Having witnessed Nai's skills, king Mangra set him free.

This tale has been passed across generations. Some people even believe Nai Khanom Tom could beat any number of opponents, even mythic Thai creatures.

As a big Muay Thai fan, you want to verify this claim. Suppose Nai Khanom Tom has H hit points and has to duel against N Rajasis. Each of them has xi hit points and yi recovery points. To win a fight, Nai's hit points must be greater than the Rajasi's. After fighting, Nai loses xi hit points and recovers yi points afterwards. Moreover, Nai knows K spells that can instantly beat a Rajasi. However, when a spell is used, Nai does not lose nor wins hit points as in a usual fight.

Given the description of a set of N Rajasis, you must decide if Nai Khanom Tom can beat them all. Note that Nai Khanom Tom can choose to fight the Rajasis in any order he wants.


The input is composed of many instances. The first line of the input contains an integer T which indicates the number of instances.

The first line of each instance contains 3 integers, N (1 ≤ N ≤ 2000), H (0 ≤ H < 109) and K (1 ≤ K ≤ 2000), where H represents the initial value of Nai's hit points. Each of the N following lines contain 2 integers, xi and yi (1 ≤ xi, yi < 109).


For each instance, print a single line containing a single character. Print 'Y' if Nai Khanom Tom can beat all the Rajasis; print 'N' otherwise.

Input Sample Output Sample

2 10 2
20 10
100 1
2 10 0
9 10
10 1