 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
Third qualification round completed
Tasks
Show one task per page / all tasks on one page
Time limit  1 second 

Memory limit  256 megabytes 
Vasya has started playing a new video game. In the end of the first level he is taking a combat with the level boss. He needs to win the combat to continue playing. Vasya has a squad of n heroes, the ith of them has h_{i} hit points and a_{i} attack points. The boss has H hit points and A attack points.
The combat goes as follows.
 If Vasya has no more heroes, he loses the game.
 If he still has at least one hero, he can choose any one and send it to fight against the boss;
 If Vasya has chosen the ith hero, the combat proceeds as follows:
 The hero attacks the boss and reduces its hit points by a_{i};
 If the boss is still alive — has strictly positive hit points — it attacks the hero and reduces its hit points by A;
 While the hero and the boss are both still alive, the attacks are repeated.
 If the boss is dead, the combat is over, Vasya wins. In the other case all of the actions are repeated.
Vasya doesn't want to lose many heroes at the very first level of the game. So he wants to plan the combat to lose the minimum possible number of heroes. Help him to find what is the minimal number of heroes that he can lose but still defeat the boss. If Vasya cannot defeat the boss even losing all of his heroes, output  1.
Let us consider sample test cases.
In the first test case the optimal plan is the following: first send hero 2 to the combat. It attacks the boss three times, reduce its hit points by 12, and then dies. After that Vasya must send hero 3 to the combat, it immediately reduces the hit points of the boss by 6, and the boss dies. Therefore Vasya loses one hero only.
In the second test case Vasya cannot kill the boss, no matter in which order he sends his heroes to the combat.
Input format 
Input data contains multiple test cases. The first line contains one integer t — the number of test cases (1 ≤ t ≤ 1000). Each of the t test cases is described in the following way. The first line of the description contains three integers n, H and A — the number of heroes Vasya has, the number of hit points of the boss, and the number of attack points of the boss (1 ≤ n ≤ 10^{5}, 1 ≤ H, A ≤ 10^{9}). Each of the following n lines contains two integers h_{i}, a_{i} — number of hit points and attack points of the ith hero (1 ≤ h_{i}, a_{i} ≤ 10^{9}). The sum of values of n in all test cases of one input data doesn't exceed 10^{5}. 

Output format 
For each test case output either the minimal number of heroes that Vasya must lose to defeat the boss, or  1 if Vasya cannot defeat the boss. 
Examples 
Input data
2 4 18 4 4 5 9 4 1 6 3 3 4 27 4 4 5 9 4 1 6 3 3
Output data
1 1 
