Treasure in the Caves#1203
An explorer is investigating an ancient cave filled with treasures. The cave has rooms, each containing treasures worth M_j gold coins. However, each room has traps, and the probability of triggering a trap is P_j. If at least one trap is triggered, the explorer will lose all collected treasures.
An experienced guide has advised that the total probability of triggering a trap should not exceed , otherwise the journey becomes too dangerous.
What is the maximum amount of gold the explorer can collect without exceeding the acceptable risk level?
The first line contains (0 < T \leq 100), the number of test cases. For each test case, the first line contains (0.0 \leq P \leq 1.0), the maximum allowable probability, and (0 < N \leq 100), the number of rooms in the cave. The next lines each contain an integer M_j (0 < M_j \leq 100) and a real number P_j (0.0 \leq P_j \leq 1.0). Room contains M_j gold coins, and the probability of triggering a trap is P_j.
After visiting a room, its treasures are taken. All probabilities are independent.
For each test case, print the maximum number of gold coins that can be collected such that the probability of triggering a trap remains below the given limit. Each answer should be printed on a separate line.
Example 1