Arseniy 提出了另一个商业计划 - 从自动售货机出售苏打水!为此,他购买了一台带有 $$$n$$$ 架子的机器,以及 $$$k$$$ 瓶子,其中第 $$$i$$$ 个瓶子的特征是品牌索引 $$$b_i$$$ 和成本 $$$c_i$$$。
每个架子上可以放置任意数量的瓶子,但同一架子上的所有瓶子必须是同一品牌。
Arseniy 知道他放在机器货架上的所有瓶子都会被出售。因此,他让你计算一下他最多能赚到多少钱。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$),其中 $$$n$$$ 是机器中的货架数量,$$$k$$$ 是 Arseniy 可用的瓶子数量。
接下来的 $$$k$$$ 行包含两个整数 $$$b_i$$$ 和 $$$c_i$$$ ($$$1 \le b_i \le k, 1 \le c_i \le 1000$$$) — 第 $$$i$$$ 瓶的品牌和成本。
还保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,并且所有测试用例的 $$$k$$$ 总和也不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——Arseniy 可以获得的最大金额。
示例
输入 #1
4 3 3 2 6 2 7 1 15 1 3 2 6 2 7 1 15 6 2 1 7 2 5 190000 1 1 1000
输出 #1
28 15 12 1000
注意
在第一个测试用例中,Arseniy 在自动售货机中有 $$$3$$$ 货架。例如,他可以将两瓶品牌$$$2$$$放在第一个货架上,并将一瓶品牌$$$1$$$放在第二个货架上。那么瓶子的总成本将为 $$$6 + 7 + 15 = 28$$$。
在第二个测试用例中,他只有一个架子。不难看出,最佳选择是在上面放一瓶 $$$1$$$ 品牌的酒。那么总成本将为$$$15$$$。
在第三个测试用例中,他有多达 $$$6$$$ 的架子,因此他可以放置所有可用的瓶子,总成本为 $$$7 + 5 = 12$$$。