这两天京东618有大优惠，小明同学想买一些物品。他身上有ｎ元，这里有ｍ件物品。每件物品有两个属性分别before:原价，now:现价 (before, now都为正整数)。他想知道他买到的物品最大原价和（每一件物品不能买多件）

第一行一个数字Ｔ (0<T<=10)，表示Ｔ组测试数据。

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