Solution 1

Classify the jewels by their colors, and define, for each color, the jewel with the highest value as the representative of the color. (If there are multiple of them, pick any one.) Sort the representatives in descending order of their values, and mark \(M\) jewels with the highest values.

Then there exists an optimal choice that chooses all the marked jewels. (★)

Admitting this claim for now, consider how to determine such an optimal choice. By choosing the marked \(M\) jewels, the constraint on the minimum distinct colors is satisfied, so all that left is to sort the unmarked jewels in descending order of their values, and choosing \((M-K)\) jewels with the highest values.

The main bottleneck is sorting. By using standard library for sorting, the time complexity should be \(O(N \log N)\).

Solution 2

There are different algorithms that yield the same result. An example is the following:

1. Pick \(K\) jewels with the highest values (ignoring the colors for now).
2. Repeat the following until there are \(M\) or more distinct colors:
   • Among the chosen jewels, discard a jewel with the lowest value among the non-representatives, and choose a jewel with the highest value among the representatives.

Sample code

The following is sample implementation of solution 1 in Python.

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

Proof of (★)

Suppose you were given a legal choice of jewels (\(K\) jewels with \(M\) or more distinct colors).

For each color included in the choice, if the representative of that color is not included, we can swap one of the chosen one with the representative.

At this point, at least \(M\) or more representatives are chosen. If any of the \(M\) marked jewels is not chosen, at least one unmarked representative is chosen. By repeatedly swapping the unmarked representative with a marked one, all the marked representatives are eventually chosen.

In the course of these modifications, the total value of the chosen jewels never decreases. (Of course, the number of the chosen jewels remains invariant, and the choice is kept legal.) Therefore, by taking a legal choice that maximizes the total value and following the process above, we obtain the conclusion (★).