{"raw_statement":[{"iden":"statement","content":"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.\n\nBurma'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.\n\nThis tale has been passed across generations. Some people even believe Nai Khanom Tom could beat any number of opponents, even mythic Thai creatures.\n\nAs 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.\n\nGiven 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.\n\nThe first line has a single integer T, the number of test cases.\n\nFor 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, xi and yi.\n\n*Limits* \n\nFor each test case, print a single line with _Y_ if it is possible for Nai Khanom Tom to beat all Rajasis; print _N_ otherwise.\n\n"},{"iden":"input","content":"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, xi and yi.*Limits*   1 ≤ T ≤ 100  1 ≤ N ≤ 2·103  0 ≤ K ≤ N  The sum of N across all test cases will not exceed 2·104.  0 ≤ H, xi, yi ≤ 109 "},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N, H, K \\in \\mathbb{Z} $ denote the number of Rajasis, Nai’s initial hit points, and the number of instant-kill spells, respectively.  \n- Let $ R = \\{(x_i, y_i) \\mid i \\in \\{1, \\dots, N\\}\\} $ be the set of Rajasis, where $ x_i $ is the hit points of Rajasi $ i $, and $ y_i $ is its recovery points.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{some bound (unspecified)} $  \n2. For each test case:  \n   - $ 1 \\le N \\le \\text{some bound (unspecified)} $  \n   - $ 1 \\le H \\le \\text{some bound (unspecified)} $  \n   - $ 0 \\le K \\le N $  \n   - $ 1 \\le x_i, y_i \\le \\text{some bound (unspecified)} $  \n\n**Objective**  \nDetermine if there exists an ordering $ \\pi \\in S_N $ (permutation of Rajasis) and a subset $ S \\subseteq \\{1, \\dots, N\\} $ with $ |S| \\le K $ such that, using spells on Rajasis in $ S $ (bypassing combat), and fighting the rest in order $ \\pi $, Nai’s hit points never drop to 0 or below during the sequence, and for each fought Rajasi $ i \\notin S $, his current hit points > $ x_i $ before the fight.  \n\nAfter each fought Rajasi $ i \\notin S $:  \n- Nai’s hit points decrease by $ x_i $, then increase by $ y_i $.  \n\nFormally, define a sequence of hit points $ H_0 = H $, and for $ j = 1 $ to $ N $:  \n- If Rajasi $ \\pi(j) \\in S $: $ H_j = H_{j-1} $  \n- Else:  \n  - If $ H_{j-1} \\le x_{\\pi(j)} $: fail  \n  - Else: $ H_j = H_{j-1} - x_{\\pi(j)} + y_{\\pi(j)} $  \n\nOutput \"Y\" if such $ \\pi $ and $ S $ exist; \"N\" otherwise.","simple_statement":"Nai Khanom Tom has H hit points and must fight N Rajasis.  \nEach Rajasi has xi hit points and yi recovery points.  \nTo win a fight: Nai’s current hit points > Rajasi’s xi.  \nAfter winning: Nai loses xi, gains yi.  \nNai has K spells that can instantly beat a Rajasi without changing hit points.  \nNai can choose any order to fight.  \nCan he beat all Rajasis? Print Y or N.","has_page_source":false}