13342: 偷银行

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

有个小偷研究了几个月了,他一直在评估各银行的安全和现金持有量。他想做一个计算风险,并抓住尽可能多的

钱。每个银行最多只可以被偷一次。可是他偷每家银行总是有一定的概率被抓,现在给了你一个概率P,只要他

被抓的概率乘积不大与P,他就是安全的。

Input

有多组数据,输入的第一行给出了T,(T个情况)。对于每一个情况下,输入的第一行给出一个浮点数P,和一

个整数n,n为计划的银行数量。接下来n行,其中给出了一个整数PJ(钱数)MJ(被抓概率)。

注:0 < T <= 10
0.0 <= P <= 1.0
0 < N <= 10
0 < Pj <= 10
0.0 <= Mj <= 1.0


Output

对于每个测试用例,输出他可以在安全的情况下,并偷到的最大钱数

Sample Input Copy

3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05
2
0.04 2
1 0.02
3 0.02
0.05 2
1 0.02
2 0.03

Sample Output Copy

2
4
6
4
3