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

## 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