← 返回题目列表

AtCoder · abc461_c

C. 品种

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

分数: 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

小心溢出。