Woburn Challenge 2018-19 Round 3 - Senior Division
Problem 1: The Perfect Team
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 ≤ N ≤ 300,000) Pokémon. There are K (1 ≤ K ≤ N) different Pokémon types, numbered from 1 to K. The i-th Pokémon has type Ti (1 ≤ Ti ≤ K), and level Li (1 ≤ Li ≤ 109). There's at least one Pokémon of each type 1..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 ≤ M ≤ 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..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.
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, Ti and Li, for i = 1..N.
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
In the first case, the 2nd, 3rd, and 4th Pokémon should be chosen. All Pokémon types 1..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 1st, 3rd, 4th, 5th, and 7th Pokémon should be chosen.
Point Value: 10 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Feb 01, 2019
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3