解法 1

宝石を色ごとに分類し、各色について価値が最高の宝石（複数ある場合はそのうち一つ）をその色の代表とします。色を代表する宝石を価値の降順にソートし、価値の高い方から \(M\) 個に印をつけます。

このとき、印つきの宝石をすべて選ぶような選び方の中に、求めるべき最適な選び方が存在します。（★）

このことをひとまず認めて、そのような最適な選び方を求めます。印つきの宝石 \(M\) 個を選んだ時点で色の種類数の要件は満たされるため、あとは印なしの宝石を価値の降順にソートし、価値の高い方から \(K - M\) 個を選ぶのが最適です。

主に時間がかかる処理はソートであり、それに標準ライブラリを使えば時間計算量は \(O(N \log N)\) となるはずです。

解法 2

上と異なるアルゴリズムで同じ結果を得ることもできます。例えば次のアルゴリズムが考えられます。

1. （いったん色を無視して）価値の高い順に宝石を \(K\) 個選ぶ。
2. 選んだ宝石の色が \(M\) 種類以上になるまで次を繰り返す。
   • 選択中の宝石の中から「色の代表でない宝石のうち価値最低のもの」を捨て、未選択の宝石の中から「色の代表である宝石のうち価値最高のもの」を選ぶ。

実装例

Python での解法 1 の実装例です。

N, K, M = map(int, input().split())
t = [[] for _ in range(N + 1)]
for i in range(N):
    C, V = map(int, input().split())
    t[C].append(V)

top = []
tail = []
for r in t:
    if len(r) > 0:
        r.sort(reverse=True)
        top.append(r[0])
        tail += r[1:]

top.sort(reverse=True)
tail += top[M:]
tail.sort(reverse=True)
print(sum(top[:M]) + sum(tail[: K - M]))

（★）の証明

合法的な宝石の選び方（色が \(M\) 種類以上の \(K\) 個の宝石）が与えられたとします。

まず、一つ以上の宝石を選んでいる各色について、もしその色の代表を選んでいなければ、その色の宝石のうちどれか一つと入れ替えに代表を選ぶことにします。

この時点で、\(M\) 個以上の代表が選ばれています。従って、\(M\) 個ある印つきの宝石の中に選んでいないものがあるなら、なにか印なしの代表を選んでいることになります。その印なしの代表の代わりに印つきの宝石を選ぶことにするのを繰り返すと、すべての印つきの宝石が選ばれます。

以上の過程で、選ぶ宝石の価値の総和が減ることはありません（もちろん選ぶ宝石の個数は変わらず、選び方は合法的なままです）。よって、合法的な宝石の選び方のうち総価値が最大のものをなにか一つとって上記の過程を辿ると結論（★）が得られます。