有志向的强盗 Roy 看过很多美国电影，他知道坏人最终通常会被抓住，这往往是因为他们变得太贪婪了。他决定只在银行抢劫这个利润丰厚的行业工作一小段时间，然后就退休去大学找一份舒适的工作。

几个月来，Roy 一直在评估各家银行的安保情况以及它们持有的现金数额。他想要进行一次经过计算的冒险，尽可能多地抢钱。他的母亲 Ola 设定了一个可容忍的被捕概率。她认为，只要他抢劫的银行加起来的被捕概率低于这个值，他就是安全的。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个场景，输入的第一行给出一个浮点数 $P$，表示 Roy 需要保持的被捕概率上限，以及一个整数 $N$，表示他计划抢劫的银行数量。接下来有 $N$ 行，其中第 $j$ 行给出一个整数 $M_j$ 和一个浮点数 $P_j$。银行 $j$ 内存有 $M_j$ 百万美元，抢劫该银行被捕的概率为 $P_j$。

输出格式

对于每个测试用例，输出一行，表示在被捕概率低于设定上限的前提下，他所能期望抢到的最大金额（以百万美元为单位）。

数据范围

• $0 < T \leq 100$
• $0.0 \leq P \leq 1.0$
• $0 < N \leq 100$
• $0 < M_j \leq 100$
• $0.0 \leq P_j \leq 1.0$
• 银行一旦被抢就会破产，你可以假设所有概率都是独立的，因为警察的资金非常有限。

样例

输入 1

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

输出 1

2
4
6