C - Variety 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

N 個の宝石があります。i 番目の宝石の色（整数で表されます）は C_i で価値は V_i です。

この N 個の宝石の中から K 個を選びます。ただし、選んだ宝石の色が 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

この例では 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

宝石や選ぶ個数は入力例 1 と同じですが、選んだ宝石の色が 3 種類以上なければなりません。

宝石 3, 4, 5 を選ぶと、それらの色は 1, 2, 3 で 3 種類あります。それらの価値の総和は 50 + 10 + 20 = 80 で、これがありうる最大値です。

入力例 3

5 5 1
4 1000000000
5 1000000000
4 1000000000
5 1000000000
4 1000000000

出力例 3

5000000000

オーバーフローに注意してください。

Score : 300 points

Problem Statement

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.)

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.

Input

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

Output

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

Sample Input 1

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

Sample Output 1

110

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 Input 2

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

Sample Output 2

80

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 Input 3

5 5 1
4 1000000000
5 1000000000
4 1000000000
5 1000000000
4 1000000000

Sample Output 3

5000000000

Beware of overflow.