84423 - Robberies
时间限制 : 1 秒
内存限制 : 128 MB
心怀梦想的罗伊（Roy the Robber）看过很多美国电影，知道坏人通常最终都会被抓住，往往是因为他们太贪婪了。他决定只在银行抢劫这个利润丰厚的行业里干一小段时间，然后就退休去大学找一份舒适的工作。
几个月来，罗伊一直在评估各家银行的安全措施以及它们持有的现金数额。他想要做出一个有把握的风险决策，尽可能多地抢到钱。
他的母亲奥拉（Ola）决定了一个可以接受的被抓概率P。她认为，如果罗伊抢劫的所有银行综合起来的（总）被抓概率小于这个阈值，那么他就是足够安全的。
提示：罗伊没被抓的概率等于所有等于抢劫了的银行的未被抓的概率的乘积。
输入
第一行输入一个整数T，表示测试用例的数量。
对于每个测试用例：
第一行输入一个浮点数P（罗伊需要低于的被抓概率上限）和一个整数N（他计划考虑的银行数量）。
接下来N行，其中第j行给出一个整数M_j（第j家银行的现金数额，单位：百万）和一个浮点数P_j（抢劫该银行时被抓的概率）。
输出
对于每个测试用例，输出一行，包含在总被抓概率低于设定上限的条件下，他最多能期望抢到多少百万现金
样例
输入
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 4 6
提示
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < M_j <= 100
0.0 <= P_j <= 1.0
一家银行如果被抢就会破产，并且你可以假设所有概率都是相互独立的，因为警方的资源非常有限。
来源
IDI