Robberies

Roy plans to rob banks for a short while, then retire to a quiet job at a university. For months he has measured how much cash each bank holds and how risky it is to rob it.

His mother Ola set a limit on the risk she tolerates. Roy may rob any set of the banks, each bank at most once, as long as the probability that he is caught stays strictly below that limit. The banks are independent, so if he robs the set $S$ of banks, the probability of getting caught is $1 - \prod_{j \in S} (1 - P_j)$.

Find the largest total amount of money Roy can take.

The first line contains the number of test cases $T$.

Each test case starts with a line holding a real number $P$ and an integer $N$. $P$ is the limit Roy must stay below and $N$ is the number of banks he has plans for. Each of the next $N$ lines holds an integer $M_j$ and a real number $P_j$. Bank $j$ holds $M_j$ millions, and robbing it has probability $P_j$ of getting caught.

• $0 < T \le 100$
• $0.0 \le P \le 1.0$
• $0 < N \le 100$
• $0 < M_j \le 100$
• $0.0 \le P_j \le 1.0$
• Every real number in the input has at most two digits after the decimal point.

A bank goes bankrupt once it is robbed, so Roy robs each bank at most once.

For each test case print one line with the largest number of millions Roy can take while the probability of getting caught stays strictly below $P$. If no set of banks meets that requirement, print 0.