AIOC Banner

Problem: Restaurants II

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

Restaurants II: Acquired Tastes

Input File: restin.txt
Output File: restout.txt
Time Limit: 1 second

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 si and ti, respectively.

The room happiness is the sum of all the values of si for dishes sent to the students' table, plus the sum of all the values of ti 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:

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:


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 si and ti, 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.

Sample Input 1

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

Sample Input 2

3 1 3
-2 4
4 -8
17 14

Sample Output 1


Sample Output 2



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

Page generated: 24 May 2019,  4:22am AEST