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

Constraints

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.

Input

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.

Output

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

Sample Input 2

Sample Output 1

Sample Output 2

Explanation

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.

Scoring

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