Little Elephant and Boxes
All submissions for this problem are available.
Little Elephant from Zoo of Lviv has n boxes. He don't know what is in the boxes, but he thinks that i-th box (0-based numeration) contains Vi dollars. The probability that i-th box will contain money is Pi percents. Instead of money i-th box may contain a single diamond (with the probability 100-Pi percents).
There are m things to buy, numbered from 0 to m-1, j-th thing costs exactly Cj dollars plus Dj diamonds. Little Elephant is very smart and if he has some number of dollars and diamonds he will always buy the maximal possible number of things he can afford. Note that there is just one copy of all m things.
Help Little Elephant to find the expected number of things he will buy.
First line of the input contains single integer T - the number of test cases. T test cases follow. First line of each test case contains pair of integers n and m. Next n lines of each test case contain pairs of integers Vi and Pi, one pair per line. Next m lines of each test case contain pairs of integers Cj and Dj, one pair per line.
In T lines print T real numbers - the answers for the corresponding test cases. Round each number to 4 digits after decimal point.
1 <= T <= 5
2 <= n <= 30
1 <= m <= 30
1 <= Vi, Cj <= 10^7
0 <= Dj <= 30
0 <= Pi <= 100
Input: 2 2 2 2 50 2 100 2 0 2 0 2 2 2 100 2 50 0 2 0 1 Output: 1.5000 0.5000
|Tags||hard, may12, witua|
|Time Limit:||0.560976 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.