AT_abc461_c.Variety

There are $N$ gems. The color (represented as an integer) of the $i$-th gem is $C_i$ and its value is $V_i$.

Choose $K$ gems from these $N$ gems. Here, the chosen gems must have at least $M$ distinct colors.

Find the maximum possible total value of the chosen gems. (Such a choice is always possible in the given input.)

有 $N$ 颗宝石。第 $i$ 颗宝石的颜色（用一个整数表示）为 $C_i$，其价值为 $V_i$。

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

求所选宝石的总价值的最大可能值。（题目保证输入数据下总存在满足条件的选择。）

The input is given from Standard Input in the following format:

$N$ $K$ $M$
$C_1$ $V_1$
$C_2$ $V_2$
$\vdots$
$C_N$ $V_N$

输入从标准输入中按以下格式给出：

$N$ $K$ $M$
$C_1$ $V_1$
$C_2$ $V_2$
$\vdots$
$C_N$ $V_N$

Output the maximum possible total value of the chosen gems as an integer.

输出所选宝石的最大可能总价值（整数）。

Sample 1 Explanation:
In this sample, choose three gems from five gems. The chosen gems must have at least two distinct colors.

Choosing gems $2, 3, 5$ gives colors $1, 1, 3$, which are two distinct colors. Their total value is $40 + 50 + 20 = 110$, and this is the maximum possible value.

Sample 2 Explanation:
The gems and the number to choose are the same as in Sample Input 1, but the chosen gems must have at least three distinct colors.

Choosing gems $3, 4, 5$ gives colors $1, 2, 3$, which are three distinct colors. Their total value is $50 + 10 + 20 = 80$, and this is the maximum possible value.

Sample 3 Explanation:
Beware of overflow.

Constraints

• $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$
• There exist gems of at least $M$ distinct colors.
• All input values are integers.

样例 1 解释：
本样例中，需从五颗宝石中选出三颗，且所选宝石的颜色种类数至少为两种。

选择宝石 $2, 3, 5$，对应颜色为 $1, 1, 3$，共两种不同颜色。其总价值为 $40 + 50 + 20 = 110$，这是可能的最大值。

样例 2 解释：
宝石集合及需选择的宝石数量与样例输入 1 相同，但所选宝石的颜色种类数至少为三种。

选择宝石 $3, 4, 5$，对应颜色为 $1, 2, 3$，共三种不同颜色。其总价值为 $50 + 10 + 20 = 80$，这是可能的最大值。

样例 3 解释：
注意整数溢出问题。

约束条件

• $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$ 种不同颜色的宝石。
• 所有输入值均为整数。