分数: 300 点
问题陈述
有 N 宝石。的颜色(表示为整数) i-th 宝石是 C_i 其值为 V_i.
选择 K 这些宝石 N 宝石。在这里,所选择的宝石必须至少有 M 不同的颜色。
找出所选宝石的最大可能总价值。 (在给定的输入中,这样的选择总是可能的。)
约束
- 1 \leq M \leq K \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq N
- 1 \leq V_i \leq 10^9
- 存在的宝石至少为 M 不同的颜色。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K M C_1 V_1 C_2 V_2 \vdots C_N V_N
输出
以整数形式输出所选宝石的最大可能总值。
示例输入 1
5 3 2 1 30 1 40 1 50 2 10 3 20
示例输出 1
110
在此示例中,从五颗宝石中选择三颗宝石。所选宝石必须至少具有两种不同的颜色。
选择宝石 2, 3, 5 给出颜色 1, 1, 3,这是两种不同的颜色。它们的总价值是 40 + 50 + 20 = 110,这是最大可能值。
示例输入 2
5 3 3 1 30 1 40 1 50 2 10 3 20
示例输出 2
80
要选择的宝石和数量与示例输入 1 中的相同,但所选宝石必须至少具有三种不同的颜色。
选择宝石 3, 4, 5 给出颜色 1, 2, 3,这是三种不同的颜色。它们的总价值是 50 + 10 + 20 = 80,这是最大可能值。
示例输入 3
5 5 1 4 1000000000 5 1000000000 4 1000000000 5 1000000000 4 1000000000
示例输出 3
5000000000
小心溢出。