SP2031 YKH - Please help You-Know-Who

N/A

The first line contains the number of testcases, which shall be less than 20. The testcases follow. (Possible empty lines between testcases should be ignored.) The first line of each testcase input contains two non-negative integers: the bribe B and the number of clients C. The next C lines describe each client by two positive integers a\[i\] and b\[i\] (on line i). You are guaranteed that all numbers in the input are at most 2000.

For each testcase the output is a single number, the maximum profit of You-Know-Who, and it should be written on a line by itself. The answer should have either an absolute or a relative error less than 1e-6.