Little Elephant and Boxes

时间限制:10s      空间限制:128MB

题目描述

利沃夫动物园的小象有n个盒子,每个盒子里有一些钱或者钻石。他不知道每个盒子里具体是什么,但他知道如果打开第i个盒子,他有Pi / 100的概率能获得Vi美元的钱,而有(1 – Pi / 100)的概率能获得一个钻石。现在有m个物品,分别编号为0m – 1 j个物品需要花费恰好Cj美元的钱和Dj个钻石。小象非常聪明,当他获得了一定量的钱和钻石后,他总会买尽可能多的物品。注意,每个物品只能购买一次。现在请你帮助小象计算出,当他打开所有的盒子后,他期望能够买到的物品个数是多少?


输入格式

输入的第一行包含一个正整数T,表示数据组数。
对于每组数据,第一行包含两个正整数n, m,分别表示盒子数与物品数。接下来n行,每行为两个整数Vi, Pi,分别表示小象能从第i个盒子中获得钱的数量与获得钱的概率。接下来m行,每行为两个整数Cj, Dj,分别表示第j个物品所需要的钱和钻石的数量。


输出格式

输出总共T行。每行为一个实数,为对应的测试数据的答案,实数四舍五入保留到小数点后4位。


样例输入

2
2 2
2 50
2 100
2 0
2 0
2 2
2 100
2 50
0 2
0 1

样例输出

1.5000
0.5000

提示

1≤T≤5,   2≤n≤30,   1≤m≤30

1≤Vi, Cj≤107,   0≤Dj≤30,   0≤Pi≤100

 


题目来源

没有写明来源