After the departure of David Moyes as coach of Manchester United, the board of Manchester United is looking for a new coach for the team. As usual, who could be a better option in the entire world than our little own Little Jhool? Now, Little Jhool needs to rebuild Manchester United; for that he needs to buy new players. But, wait... Little Jhool is NO ordinary coach, he's a smart, tactical, egoistical coach. But, since he's the only one who can rebuild Manchester United, he's worth the risk.

Little Jhool has been waiting for the transfer season to come soon so that he can buy some of the players he's shortlisted. He has exactly n players in his mind, and he has to buy k players out of those n players. Every player has two attributes, and both of them are known to Little Jhool already:

1. Probability of accepting the offer.
2. Amount of money they'll ask for.

Since, Little Jhool is an egoistic coach, once a player rejects his offer, he will NOT offer any contract to that player again. Since, the board has given him a fixed budget in million pounds, he cannot overspend even a single penny . Also, if he approaches a player with a given contract, irrespective of the player accepting his offer, or not - that particular amount will be deducted from his sanctioned amount. After each contract sending, Little Jhool obviously waits to know if his offer was accepted or not.

With all this information given to you, can you tell Little Jhool the probability of this entire transfer window being a successful one?

Input format:
The first line contains, tc, the number of test cases. Following that, in every test case, there will be three integers.
No. of players he's shortlisted.
No. players he wants to buy.
Total amount of money, sanctioned by the Manchester United board.

Following that, every player's attributes will follow, which will contain two integers again.
1. The price of a player.
2. The probability that he'll agree to come to Manchester United.

Output format:
For every test case, you need to print the probability of Little Jhool being able to buy the number of players he needs. This number will be a floating point number. And it should be accurate up to 10^-6 precision.

Constraints:
1 ≤ No. of shortlisted players ≤ 16
1 ≤ No. of players he wants to buy ≤ 16
1 ≤ Total money sanctioned to Little Jhool ≤ 1000
1 ≤ Price of each player ≤ 1000
1 ≤ Probability of each player being bought ≤ 100

PS: The author supports Netherlands in this FIFA 14, who do you support? ;)SAMPLE INPUT
2
3 2 100
15 75
40 80
55 50
4 3 500
150 40
150 50
150 60
150 70

SAMPLE OUTPUT
0.600000
0.210000

见题面

见题面