eolymp
bolt
Try our new interface for solving problems

Bribe

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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?

Giriş verilənləri

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 (1n, c16 and 1m1000): 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 (0b1000 and 0p100): the amount of money you need to bribe each henchman, and the probability (as a percentage) that he will be successfully converted, respectively.

Çıxış verilənləri

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.

Nümunə

Giriş verilənləri #1
2
4 3 1000
300 40
300 50
300 60
300 70
4 2 1000
100 80
700 50
400 20
500 20
Çıxış verilənləri #1
0.21
0.408
Mənbə The 2013 Benelux Algorithm Programming Contest, BAPC 2013