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
Pokémon. There are
different
Pokémon types, numbered from
to
. The
-th Pokémon has type
, and level
.
There's at least one Pokémon of each type
.
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
of the
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
-Pokémon team must include at least one Pokémon of each type
.
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 -bit signed integer.
Subtasks
In test cases worth of the points,
.
Input Specification
The first line of input consists of three space-separated integers, ,
, and
.
lines follow, the
-th of which consists of two space-separated
integers,
and
, for
.
Output Specification
Output a single integer, the maximum sum of Pokémon levels which a valid
team of 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 nd,
rd, and
th Pokémon should be chosen. All
Pokémon types
are represented, and the sum of these Pokémon's
levels is
, which is the largest achievable sum.
In the second case, the st,
rd,
th,
th, and
th Pokémon should be
chosen.
Comments