Woburn Challenge 2018-19 Round 3 - Senior Division

Jessie, James, and Meowth, members of the honourable Team Rocket, have finally hit the jackpot! They've managed to steal a group of $N$ $(1\le N\le 300000)$ Pokémon. There are $K$ $(1\le K\le N)$ different Pokémon types, numbered from $1$ to $K$. The $i$-th Pokémon has type $T_i$ $(1\le T_i\le K)$, and level $L_i$ $(1\le L_i\le {10}^9)$. There's at least one Pokémon of each type $1\dots K$.

What remains is for Team Rocket to make the best use of their haul. They can't necessarily afford to carry around that many Pokémon with them, so they'd like to choose exactly $M$ $(K\le M\le N)$ of the $N$ Pokémon to form an unstoppable battling team. Putting all of the highest-level Pokémon to use would be nice, but Team Rocket's top priority is putting together a team which has no glaring weaknesses. To make sure they're covered against anything they might face, they insist that their $M$-Pokémon team must include at least one Pokémon of each type $1\dots K$.

Subject to those conditions, help Team Rocket determine the maximum sum of Pokémon levels which such a team could possibly have! Please note that the answer may not fit within a $32$-bit signed integer.

Subtasks

In test cases worth $7/14$ of the points, $M=K$.

Input Specification

The first line of input consists of three space-separated integers, $N$, $M$, and $K$.
$N$ lines follow, the $i$-th of which consists of two space-separated integers, $T_i$ and $L_i$, for $i=1\dots N$.

Output Specification

Output a single integer, the maximum sum of Pokémon levels which a valid team of $M$ Pokémon can have.

Sample Input 1

5 3 3
1 8
2 5
1 13
3 5
2 4

Sample Output 1

23

Sample Input 2

7 5 2
1 11
2 10
1 16
2 11
1 19
1 7
2 15

Sample Output 2

72

Sample Explanation

In the first case, the $2$nd, $3$rd, and $4$th Pokémon should be chosen. All Pokémon types $1\dots 3$ are represented, and the sum of these Pokémon's levels is $5+13+5=23$, which is the largest achievable sum.

In the second case, the $1$st, $3$rd, $4$th, $5$th, and $7$th Pokémon should be chosen.