问题 G: 小明的买卖

问题 G: 小明的买卖

时间限制: 1 Sec  内存限制: 128 MB
提交: 32  解决: 6
[状态] [讨论版] [提交] [命题人:]
题目描述
这两天京东618有大优惠,小明同学想买一些物品。他身上有n元,这里有m件物品。每件物品有两个属性分别before:原价,now:现价 (before, now都为正整数)。他想知道他买到的物品最大原价和(每一件物品不能买多件)

输入
第一行一个数字T (0<T<=10),表示T组测试数据。
随后T组测试数据,每组测试数据第一行两个数字n,m,分别表示拥有的钱数和物品的数量。随后m行,每行两个数字before,now,表示这件物品的原价和现价。(1 <= n, m <= 1000, now <= before <= 1e5,  0 <= now <= 1000) 

输出

对于每组测试数据,输出能够买到物品的最大原价和。

样例输入 Copy
2
5 2
6 4
3 2
5 2
6 4
3 1
样例输出 Copy
6
9