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 ith box (0based numeration) contains V_{i} dollars. The probability that ith box will contain money is P_{i} percents. Instead of money ith box may contain a single diamond (with the probability 100P_{i} percents).
There are m things to buy, numbered from 0 to m1, jth thing costs exactly C_{j} dollars plus D_{j} 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.
Input
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 V_{i} and P_{i}, one pair per line. Next m lines of each test case contain pairs of integers C_{j} and D_{j}, one pair per line.
Output
In T lines print T real numbers  the answers for the corresponding test cases. Round each number to 4 digits after decimal point.
Constraints
1 <= T <= 5
2 <= n <= 30
1 <= m <= 30
1 <= V_{i}, C_{j} <= 10^7
0 <= D_{j} <= 30
0 <= P_{i} <= 100
Example
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
Author:  witua 
Tester:  subra 
Editorial  http://discuss.codechef.com/problems/LEBOXES 
Tags  hard may12 witua 
Date Added:  8042012 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions