题目描述

有 $N$ 颗宝石。第 $i$ 颗宝石的颜色为 $C_i$，价值为 $V_i$。

请从这 $N$ 颗宝石中选择 $K$ 颗，要求选出的宝石必须包含 至少 $M$ 种 不同的颜色。

求所选宝石的总价值的最大可能值。保证一定存在满足条件的选择方案。

输入格式

N K M
C_1 V_1
C_2 V_2
...
C_N V_N

输出格式

输出所选宝石的总价值的最大可能值。

输入示例 1

5 3 2
1 30
1 40
1 50
2 10
3 20

输出示例 1

110

示例 1 说明

从 $5$ 颗宝石中选出 $3$ 颗，要求颜色至少 $2$ 种。

选择宝石 $2, 3, 5$（颜色分别为 $1, 1, 3$，共 $2$ 种），总价值为 $40 + 50 + 20 = 110$，这是可能的最大值。

输入示例 2

5 3 3
1 30
1 40
1 50
2 10
3 20

输出示例 2

80

示例 2 说明

宝石与选取数与示例 1 相同，但要求颜色至少 $3$ 种。

选择宝石 $3, 4, 5$（颜色分别为 $1, 2, 3$，共 $3$ 种），总价值为 $50 + 10 + 20 = 80$。

输入示例 3

3 2 1
1 1000000000
1 1000000000
2 1000000000

输出示例 3

2000000000

示例 3 说明

请注意答案可能超出 int 范围。

约束条件

• $1 \le M \le K \le N \le 2 \times 10^5$
• $1 \le C_i \le N$
• $1 \le V_i \le 10^9$
• 存在至少 $M$ 种不同颜色的宝石
• 所有输入值均为整数