Want to try solving this problem? You can submit your code online if you log in or register.

You are the organiser for the National Debating Championships, in which schools
from across the country send their best and brightest students, accompanied by
their oldest and wisest teachers. It is the first night, and everyone takes
their seats at the trendy new restaurant called *deguSTATION*.
Two giant tables have been booked for the event: one for the students and one
for the teachers.

Alas, disaster strikes. The head chef is in a creative mood tonight, and has invented an entirely new menu. There are N different dishes being cooked, ranging from classic staples to the truly bizarre. Each dish can be sent to the students' table, the teachers' table, or neither. As organiser, you are allowed to decide which dishes go to which tables.

The tables are crowded and cannot fit too many plates in total. As such, you must send no more than A dishes to the students' table and no more than B dishes to the teachers' table. The chef has promised you that "the kitchen won't cook too many dishes", i.e. N ≤ A + B.

Furthermore, the students and teachers
have different tastes in food.
Caviar pizza is a favourite of the students, but the teachers are put off by all
the grease. Caramelised duck pâté on waffles is popular with the teachers,
but the students can't stand all the sugar. Everybody loves chocolate soufflé,
and nobody likes the chlorosulfonic acid sorbet. For each dish, you have
determined how much the students and teachers like/dislike the dish, and
represented this using a pair of integers s_{i} and t_{i},
respectively.

The room happiness is the sum of all the values of s_{i} for dishes sent to the
students' table, plus the sum of all the values of t_{i} for dishes sent to the teachers'
table.
Your task here is to determine the maximum possible room happiness that can be
achieved.

To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:

- 1 ≤ A, B ≤ 200,000, where A and B are the maximum number of dishes that can be sent to the students' and teachers' tables respectively.
- 1 ≤ N ≤ A+B, where N is the number of dishes available.
- -1,000 ≤ s
_{i}, t_{i}≤ 1,000, where s_{i}and t_{i}are the numbers described above indicating how much the students and teachers, respectively, like a particular dish.

As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large - in particular:

- For 50% of the available marks, 1 ≤ A,B ≤ 1000.

Your program should read from the file .
The first line of this file will consist of the integers N, A and B
separated by spaces.
The following N lines describe the various dishes. The ith of these lines
contains the integers s_{i} and t_{i}, separated by a space.

Your program should write to the file . Your output file should consist of a single integer: the maximum possible room happiness that can be achieved.

4 2 2 10 -20 -15 5 30 40 -10 -5

3 1 3 -2 4 4 -8 17 14

55

22

In the first sample case, we have four dishes that can be served up but at most two can be served to each of the students' and teachers' tables. By serving the first dish to the students, the second and third dishes to the teachers and silently discarding the fourth, the total room happiness is 10+5+40=55. This is the largest happiness achievable.

In the second case, the students' table only has room for one dish. If the third dish were served to the students' table and the first dish to the teachers, we would achieve a room happiness of 17+4=21. However, if we offer the second dish to the students' table instead, and give the teachers the first and third dishes, the total room happiness is 4+4+14=22.

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2023

Page generated: 21 September 2023, 11:29pm AEST