1 Problem statement
You are a coach of an athletic team with n athletes. You wish to send some of your athletes to a competition.
The rules of the competition are as follows:
• A team consists of x runners and y swimmers. • Each person is only allowed to participate in one sport; in other words a single person cannot be both a runner and a swimmer.
• The score of a team is the total time taken by all x runners and all y swimmers.
As the coach, you know that athlete i (1 ≤ i ≤ n) takes a[i] time to run and b[i] time to swim. Your task is to form the best team and find the minimum possible total time taken by choosing x runners and y swimmers.
2 Input format
The first line of the input consists three space-separated integers, n,x,y. n lines then follow. The i-th of these lines consists of two space-separated integers a[i] and b[i].
3 Output format
Output a single integer, the minimum possible total time taken by x runners and y swimmers.
4 Samples
Sample input 1
3 1 1
670 7279
1264 4798
7392 135
Sample output 1
805
Sample input 2
4 1 1
8580 8343
3721 6099
5225 4247
940 340
Sample output 2
4061
Sample input 3
5 1 1
6082 1564
4428 5648
6992 6200
3946 9225
9944 6939
Sample output 3
5510
5 Constraints
• 3 ≤ n ≤ 105
• 0 ≤ x,y ≤ n, x + y ≤ n
• 1 ≤ a[i] ≤ 104 (for all 1 ≤ i ≤ n)
• 1 ≤ b[i] ≤ 104 (for all 1 ≤ i ≤ n)
Required time complexity for full credit (5 points): O(nlogn).
Solutions which run in O(n2 logn) will receive 4 points - you will only need to pass test cases satisfying n ≤ 4000 to get these 4 points.
6 Submission instructions and grading
(Same policy as previous assignment) Submit your solution to CodeCrunch in either C++ or Java. You need to pass all test cases to get 5 points (or all test cases satisfying n ≤ 4000 to get 4 points).
The tasks will be labelled full and partial.
• If your final submission to full is correct, you will receive 5 points and your submission to partial will be ignored. If you are confident of your submission to full, you do not need to submit to partial.
• If multiple submissions are made, only the last one will be graded.
2.
You are not allowed to share code.
