## Description

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.

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

## Reviews

There are no reviews yet.