说明

龙哥一日学完高数，肚子咕咕发酵，于是来到理工北门的一家汉堡店吃汉堡。当然啦，汉堡也是不一样的，有牛肉堡，有鸡肉堡，还有鳕鱼堡、田鸡堡等等。龙哥对奇奇怪怪的东西很讨厌(田鸡堡都不吃)，所以不同的汉堡龙哥吃下后会产生不同的幸福感(比如牛肉堡的幸福感高，田鸡堡的幸福感低)，我们知道龙哥胃所能容纳的体积为V，每种汉堡都有自己的体积v和幸福感x，现在给你n种汉堡(汉堡不限量)，问你如何在保证龙哥所吃的汉堡体积总和不超过胃所容纳的体积下，产生最高的幸福感。龙哥想知道他如何吃才能保证他得到最大的幸福感呢(一本满足.jpg)

输入格式

第一行输入一个 t（0 < t < 5），表示有t组测试数据；

第二行输入2个数V, n（0 < V < 100000, 0 < n < 1000），表示龙哥胃的体积为V，汉堡种类的个数为n；

接下来n行，每行输入2个数，分别表示每种物品的幸福感和体积

输出格式

输出一个整数，表示龙哥能获得的最大的幸福感是多少

2
10 1
10 1
10 2
5 2
20 6

100
100

提示

吃汉堡也得遵循基本法那