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.
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 on a single line the Maxium Score can get for each case.
2 100 3 20 80 80 90 100 23 1000 3 0 23 900 290 99 555