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?
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.
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.
Sample Input 1 | Sample Output 1 |
---|---|
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 |