403150: GYM101047 F Fighting the Rajasi

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 x_i hit points and y_i recovery points. To win a fight, Nai's hit points must be greater than the Rajasi's. After fighting, Nai loses x_i hit points and recovers y_i 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 first line has a single integer T, the number of test cases.

For each test case, the first line contains three space-separated integers, N, H, and K, where H is Nai's initial hit points. Each of the following N lines have two space-separated integers, x_i and y_i.

Limits

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 2·10³
• 0 ≤ K ≤ N
• The sum of N across all test cases will not exceed 2·10⁴.
• 0 ≤ H, x_i, y_i ≤ 10⁹

For each test case, print a single line with Y if it is possible for Nai Khanom Tom to beat all Rajasis; print N otherwise.

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

Y
Y