Schools

Interview

Time limit2sMemory limit256 MB

Summary

Choose M cities for music schools and S other cities for sports schools to maximize the total number of attending students.

Level: Medium6 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

To support education, the administrator of a state decided to open exactly $M$ music schools and exactly $S$ sports schools. The state has $N$ different cities, and for every city you know how many students would attend a music school and how many would attend a sports school. The administrator never opens more than one school in a city, so each city gets one music school, one sports school, or no school at all.

If a music school opens in city $i$ , then $A_i$ students attend it. If a sports school opens in city $i$ , then $B_i$ students attend it.

Make the plan that maximizes the total number of students attending the new schools, and report that total.

Input

The first line contains the number of cities $N$ , the number of music schools to open $M$ , and the number of sports schools to open $S$ , separated by spaces ( $1 \le N \le 300\,000$ , $0 \le \min(M, S)$ , $M + S \le N$ ).

The $i$ -th of the next $N$ lines contains two integers $A_i$ and $B_i$ ( $1 \le A_i \le 100\,000$ , $1 \le B_i \le 100\,000$ ). $A_i$ is the number of students in city $i$ who want to study in a music school, and $B_i$ is the number who want to study in a sports school.

Output

Print one integer, the total number of students attending the new schools in an optimal plan.

Examples2

Example 1
Input
```
3 1 1
5 2
4 1
6 4
```
Expected output
```
9
```
Example 2
Input
```
7 2 3
9 8
10 6
3 5
1 7
5 7
6 3
5 4
```
Expected output
```
38
```