xy likes playing TV games,these days there comes up a problem,that is,as you know,in the game,he can get plenty of foods,which can add to the HP (Health Power) of the role, only when the HP grows full,it adds to the Score of the role, now he doesn't how to maxium the Score of when facing kinds of food, please help him.

Input
There are multiple test cases.
The first line contains an integer N(0<N<1000),followed by N cases of input, each case of input consists of: a nonnegative integer K (0<=K <= 1000) on a single line,representing the HP needed to grow full,then an integer F (0<= F<= 10000) on a single line,representing there would be F foods,then F lines follow,each line contains 2 integers,the first one H ( 0<=H<=10000) is the HP of the food, the second one S (0<= S <= 10000) is the Score of the food.

Output
Output on a single line the Maxium Score can get for each case.

Sample Input

2
100
3
20 80
80 90
100 23
1000
3
0 23
900 290
99 555

Sample Output

170
0