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 T_i (1 ≤ T_i ≤ K), and level L_i (1 ≤ L_i ≤ 10⁹). 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.

Subtasks

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

Input Format

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..N.

Output Format

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 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.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Feb 01, 2019
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)