Problem K
The Gatekeepers of Joy
The IT-University of Copenhagen (ITU) is known for its
beautiful and desirable skyboxes, which give a superior
environment for learning, working, and enjoying life.
Since the beginning of time at ITU, access to these boxes has
been known to almost wage war between colleagues and loved
ones. The one who holds the key to the boxes holds the key to
happiness at ITU. These gatekeepers, also known as FM
(Facilities Management), have for centuries had the task of
deciding how to distribute the joy. But in the last couple of
years, the pressure of this enormous responsibility has
affected their life too much. They do not sleep anymore, and
they live in constant fear, not knowing when the next employee
will jump them, trying to steal the key.
To compensate for the many years that FM has been living in
fear, ITU has decided to let FM auction access to the boxes,
and keep the profit as a bonus. The facility managers have
agreed to accept this offer, and are therefore going to create
daily auctions, where groups of people can make $B$ offers on the skyboxes they would
like to book the following day. To ensure that they receive the
maximal amount of compensation, they would like you to create a
program that computes which groups should get which rooms, such
that the accumulated prize is as high as possible.
Examples
|
Skybox |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
1 |
2 |
0 |
0 |
0 |
0 |
|
|
2 |
0 |
4 |
0 |
0 |
0 |
|
|
Groups |
3 |
0 |
6 |
0 |
0 |
0 |
|
4 |
0 |
0 |
8 |
0 |
0 |
|
|
5 |
0 |
0 |
0 |
0 |
10 |
|
|
Skybox |
|||||
|
1 |
2 |
3 |
4 |
||
|
1 |
5 |
7 |
1 |
0 |
|
|
Groups |
2 |
2 |
0 |
0 |
3 |
|
3 |
0 |
9 |
0 |
0 |
|
|
4 |
0 |
5 |
2 |
0 |
|
In example 1 above, the facility managers give Skybox1 to
group1 for the price 2, they give skybox2 to group3 for the
price 6, they give skybox3 to group4 for the price 8 and they
give box5 to group5 for the price 10. Therefore the result is
26.
In example 2 the boxes are distributed such that group1 gets
box1 for 5, group2 gets box4 for 3, group3 gets box2 for 9, and
group4 gets box3 for 2. Therefore the result is 19.
Input
First-line consists of 2 integers $G$ and $R$ separated by a single space. You can assume that $1\leq G \leq 100$ and $1\leq R \leq 100$. On each of the following $G$ lines, there will be $B$ bids of the format ’room_number’ ’:’ ’amount_bid’. You can assume that $1\leq B \leq R$, that $1\leq room\_ number \leq R$, and $1\leq amount\_ bid \leq 100$.
Output
One integer, the maximal accumulated prize.
Test groups
There are three test groups.
|
Test group 1 |
Bids are limited to $B = 1$ |
|
$G$ and $R$ is limited to $1\leq G, R \leq 8$ |
|
|
Test group 2 |
$G$ and $R$ is limited to $1\leq G, R \leq 8$ |
|
Test group 3 |
No further restrictions |
| Sample Input 1 | Sample Output 1 |
|---|---|
5 5 1:2 2:4 2:6 3:8 5:10 |
26 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 4 1:5 2:7 3:1 1:2 4:3 2:9 2:5 3:2 |
19 |
| Sample Input 3 | Sample Output 3 |
|---|---|
20 20 14:1 9:9 16:7 10:8 12:10 7:9 5:5 4:10 9:9 20:3 4:2 11:8 18:2 12:7 7:9 16:8 17:5 2:9 1:2 13:1 20:8 11:4 3:4 8:4 5:9 15:2 3:6 17:8 4:5 18:5 11:9 20:9 19:5 15:2 11:10 8:5 6:4 2:10 9:8 3:2 5:1 3:9 13:9 17:4 7:10 14:10 9:8 16:6 11:10 4:8 11:4 8:1 9:2 12:3 14:1 4:3 2:10 20:2 1:2 7:10 19:2 13:2 12:2 2:10 4:8 7:1 1:9 20:2 9:2 8:2 10:6 14:3 2:9 15:1 4:7 7:5 12:8 19:3 2:3 6:6 17:5 20:8 1:8 14:10 17:5 13:5 5:9 1:8 3:6 2:9 9:3 16:6 20:5 12:10 10:7 14:2 1:10 11:3 8:4 15:7 19:7 |
152 |
