WC '18 Contest 3 S1 - The Perfect Team

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.8s
Memory limit: 64M

Problem type
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 300\,000) 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\ldots 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\ldots 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.


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 \ldots 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


Sample Input 2

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

Sample Output 2


Sample Explanation

In the first case, the 2nd, 3rd, and 4th Pokémon should be chosen. All Pokémon types 1\dots3 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 1st, 3rd, 4th, 5th, and 7th Pokémon should be chosen.


There are no comments at the moment.