特殊的超市

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

有一个奇怪的超市,超市中有m种商品,每个商品都有一个都价格pi,超市的特殊在于:如果顾客买第i种商品,就会赠送ci个欢乐豆,一种商品对一个顾客只会赠送一次。现在有两个好朋友来超市买东西,他们都带了n元钱,如果最终两个人得到的欢乐豆不一样,他们的欢乐豆的和的最大值是多少?

Input

 首先输入一个正整数T (T<10),测试数据有T组。
对于每组测试数据的第一行有两个整数n,m ( 1 <= n,m <= 1000)。之后有m行,每行两个数字p c,代表第i种商品的价格是p,赠送的欢乐豆的数量c(1 <= p,c <= 1000).

Output

 输出一个整数,表示两个人获得的欢乐豆的和的最大值。

Sample Input

1
10 3
2 3
3 5
5 8

Sample Output

29

Hint

 第一个人可以买第1,2,3种商品,得到的欢乐豆是16,第二个人也可以买1,2,3这三种商品,但是不能和第一个人得到的欢乐豆一样,所以最多可以得到13个欢乐豆。

Source

windream