题目描述

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 能赚到的最大金额。

说明/提示

在第一个测试用例中，Arseniy 有 $3$ 个货架。他可以例如将两个品牌为 $2$ 的汽水瓶放在第一个货架，将一个品牌为 $1$ 的汽水瓶放在第二个货架。这样所有汽水瓶的总售价为 $6 + 7 + 15 = 28$。

在第二个测试用例中，他只有一个货架。不难发现最优方案是将品牌为 $1$ 的汽水瓶放在上面。这样总售价为 $15$。

在第三个测试用例中，他有 $6$ 个货架，因此可以放下所有汽水瓶，总售价为 $7 + 5 = 12$。

由 ChatGPT 4.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

28
15
12
1000