Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0039 - 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 n, c 16 and 1 m 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 b 1 000 and 0 p 100): the amount of money you need to bribe each henchman, and the probability (as a percent- age) 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 accu- rate up to 106 relative or absolute precision.

Examples

stdin

stdout

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


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-24
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Benelux (BAPC) 2013.B

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.