Little Elephant and Boxes

Problem code: LEBOXES

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.

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

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 <= Vi, Cj <= 10^7

0 <= Dj <= 30

0 <= Pi <= 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
Date Added: 8-04-2012
Time Limit: 4 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

@nokia: Statement says that

witaliy_adm @ 3 May 2012 12:21 AM
@nokia: Statement says that there are exactly n boxes, you don't 'take' any one or not.

@admin Thanks

nokia @ 3 May 2012 12:34 AM
@admin Thanks

can anyone please explain one

pikku @ 7 May 2012 02:09 AM
can anyone please explain one of the test cases?

Test case #1. First box has

zifmia @ 8 May 2012 11:50 AM
Test case #1. First box has $2 50% of time, other 50% of time it has a diamond. Second box always has $2. Total from all boxes, 50% of time you have $4, and 50% you will have $2 and a diamond. There are 2 objects you want to buy. Both cost $2, no diamonds. So 50% of time, you can afford just 1, and 50% of time, you can buy both. Average number of items you buy is 1.5. Second case the boxes are identical, but now the items cost 1 and 2 diamonds. 50% of the time you will have a diamond, and can buy one object. The other 50% you have no diamonds and buy nothing. Average objects you can buy = 0.5

if the elephant is so smart

szpraai @ 10 May 2012 08:25 PM
if the elephant is so smart as the rumor says, I belive he can solve this without my help

@szpraai: :)

witaliy_adm @ 11 May 2012 02:38 PM
@szpraai: :)

SUCCESSFUL SUBMISSIONS


Fetching successful submissions