G :: Greedy Bounty Hunter

Time Limit: 10 Seconds    Memory Limit: 65536 KB

Bounty hunter is a hero who moves from one city to another to earn money using his power.

His journey begins in the an ancient country that has N cities. He starts his mission from the city 1 in the first day, and each day he visits the next city, never going back.

At the beginning, Bounty hunter has X dollars and Y attack points. In each city, he can increase his attack points by spending money and earn some money by accepting a task. In the ith city, it costs him ai dollars to increase one point of attack. And he gets bi*yi dollars after finishing the task in that city while yi is his attack points after increasing at city i.

All that bounty hunter cares about is money. He wants to own as much dollars as he can after leaving the Nth city. Help him find out the maximal amount of money he can get.

Note that when bounty hunter leaves a city he never comes back. Also his attack points can be increased by any real numbers as long as the money is enough. For example, if he has 7 dollars and the unit price of attack point at the city he stays now is 2, he can spend 3 dollars to increase attack force by 1.5.

After Bounty hunter finishes the task he will leave the country at once. Meaning he can only increase his attack points before he finishes the task and gets the money at the same city.

Input

There are multiple test cases. The first line of the input is an integer T < 128, indicating the number of test cases. For each test case, the first line contains three integers N, X, Y, (0 ≤ N, X, Y ≤ 100000) following by N lines. In the ith line there are two real number ai and bi.(0 ≤ bi ≤ 1,0 < ai  ≤ 100000)

Output

Output the maximal amount of money bounty hunter can get to two decimal places reserved. It is guaranteed that the answer is less than 1015.

Sample Input

2
1 10 0
1.0 1.0
3 13 5
7.0 1.0
1.1 0.6
1.0 0.6

Sample Output

10.00
25.64

Submit