Problem C
Bribe

After having done a lot of spying and infiltrating a criminal network, you are now ready to try and dismantle it. This, however, requires the cooperation of a certain number of the henchmen. This in turn requires money in order to bribe them, but due to budget cuts, you only have a limited amount of money.

Fortunately, you are an excellent judge of character, so for each of the henchmen you are considering to bribe, you know what amount of money they will ask for. Furthermore, you know the probability that they will then successfully convert, as opposed to taking the money and making a run for it. There is no particular rush, so after each attempted conversion you can establish whether it was successful or not, before you move on to someone else. Of course, if it was not successful, then you cannot try to bribe this henchman a second time.

Given all this information on the henchmen, the amount of money that you have at your disposal, and the number of henchmen you need to convert, can you work out the probability that this operation will be a success?

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:

• one line with three space-separated integers $n$, $c$ and $m$ ($1 \leq n, c \leq 16$ and $1 \leq m \leq 1\, 000$): the number of henchmen that are susceptible to bribe, the number you need to convert, and the amount of money that you have, respectively.

• $n$ lines with two space-separated integers $b$ and $p$ ($0 \leq b \leq 1\, 000$ and $0 \leq p \leq 100$): the amount of money you need to bribe each henchman, and the probability (as a percentage) that he will be successfully converted, respectively.

Output

Per test case:

• one line with a single floating point number: the probability that you will succeed in converting $c$ henchmen, if you take an optimal approach. This number should be accurate up to $10^{-6}$ relative or absolute precision.

2
4 3 1000
300 40
300 50
300 60
300 70
4 2 1000
100 80
700 50
400 20
500 20

0.21
0.408