Little Elephant and Boxes
题目描述
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
<![endif]--><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:宋体;mso-ascii-font-family:
Calibri;mso-hansi-font-family:Calibri;mso-bidi-font-family:"Cambria Math";
mso-font-kerning:1.0pt">利沃夫动物园的小象有</span><span lang="EN-US" style="font-size:
10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;mso-fareast-font-family:
宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">n</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:宋体;mso-ascii-font-family:
Calibri;mso-hansi-font-family:Calibri;mso-bidi-font-family:"Cambria Math";
mso-font-kerning:1.0pt">个盒子，每个盒子里有一些钱或者钻石。他不知道每个盒子里具体是什么，但他知道如果打开第</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt">i</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">个盒子，他有</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt">Pi / 100</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">的概率能获得</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt">Vi</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">美元的钱，而有</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt">(1 – Pi / 100)</span><span style="font-size:10.5pt;mso-bidi-font-size:
11.0pt;font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">的概率能获得一个钻石。现在有</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt">m</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">个物品，分别编号为</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt">0</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">到</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt">m – 1</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">，</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt"> </span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">第</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt">j</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">个物品需要花费恰好</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt">Cj</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">美元的钱和</span><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:11.0pt;font-family:Calibri;
mso-fareast-font-family:宋体;mso-bidi-font-family:"Cambria Math";mso-font-kerning:
1.0pt">Dj</span><span style="font-size:10.5pt;mso-bidi-font-size:11.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-hansi-font-family:Calibri;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">个钻石。小象非常聪明，当他获得了一定量的钱和钻石后，他总会买尽可能多的物品。注意，每个物品只能购买一次。现在请你帮助小象计算出，当他打开所有的盒子后，他期望能够买到的物品个数是多少？</span><span lang="EN-US" style="font-size:10.5pt;
mso-bidi-font-size:11.0pt;font-family:Calibri;mso-fareast-font-family:宋体;
mso-bidi-font-family:"Cambria Math";mso-font-kerning:1.0pt">
</span></b>
输入格式
输入的第一行包含一个正整数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