🥫 Startup：货架上的罐头

📖 题目描述

你有一个共有 $n$ 层的货架，以及 $k$ 个罐头。第 $i$ 个罐头有两个属性：

• 品牌编号 $b_i$（$1 \le b_i \le k$）
• 美味度 $c_i$（$1 \le c_i \le 1000$）

你要将这些罐头摆放到货架上。每层货架可以摆 无限个 罐头，但一层上只能摆放同一种品牌的罐头。

你可以选择摆放任意数量的罐头（也可以不摆）。请你计算，如何摆放能使所有被摆上货架的罐头的美味度总和最大？

📥 输入格式

第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。

接下来的每组测试数据包含：

• 第一行两个整数 $n, k$（$1 \le n, k \le 2 \times 10^5$），表示货架层数与罐头数量；
• 接下来的 $k$ 行，每行两个整数 $b_i, c_i$，表示第 $i$ 个罐头的品牌编号和美味度。

保证：

• 所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$；
• 所有测试数据中 $k$ 的总和不超过 $2 \times 10^5$。

📤 输出格式

对于每组测试数据，输出一行一个整数，表示最大美味度总和。

🧪 样例输入

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

🔍 样例说明

样例 1：

有 3 层货架、3 个罐头，其中：

• 品牌 2 有两个罐头：美味度 6 和 7；
• 品牌 1 有一个罐头：美味度 15；

可以选择将品牌 2 的两个罐头放在一层，品牌 1 的罐头放在另一层，总美味度为 $6 + 7 + 15 = 28$。

样例 2：

只有 1 层货架，最多只能选择一个品牌。最优方案是选品牌 1 的罐头，总和为 15。

样例 3：

有 6 层货架，但只有两个罐头，可以全部放入，总美味度 $7 + 5 = 12$。