← 返回题目列表

Codeforces · 2036/B

B. 启动

中文机器翻译题面 查看原题

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$$$。