题目描述

一个劫匪要去抢劫 $n$ 家银行，每家银行有一定的现金，每抢一家银行该劫匪有一定几率被警察抓住，但是当该劫匪连续作案被抓住的几率小于等于 $p$ 时他就可以逃脱，问该劫匪在不被捕的情况下最多能抢到多少钱？

输入格式

第一行为用例组数 $T$，每组用例第一行为一个浮点数 $P$ 和一个整数 $n$ 分别表示被捕的几率上限以及该劫匪计划抢劫的银行数量。

之后 $n$ 行每行一个整数 $M$ 和一个浮点数 $p$ 表示该家银行的现金数以及该劫匪抢劫该家银行被捕的几率。

输出格式

对于每组用例，输出该劫匪在不被捕的情况最多能抢到多少钱。

样例

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 \le 100$

$0.0 \le P \le 1.0$

$0 < n \le 100$

$0 \le M_j \le 100$

$0.0 \le p_j \le 1.0$