sale

Problem Description

There are N items in the supermarket, each of them with a normal price A_i and sale price B_i.

Rar the Cat wants to buy X items during the non-sale period, and Y items during a sale period, without buying two of the same items.

Help Rar minimise the total cost of the items he buys.

Input

The first line of input will contain three integers, N, X and Y.

The next N lines of input will contain two integers each, representing A_i and B_i.

Output

The output should contain one integer, the minimum total cost.

Limits

0 ≤ X, Y ≤ N, X + Y ≤ N, 0 ≤ A_i, B_i ≤ 10⁹.

Subtask 1 (4%): 1 ≤ N ≤ 12.

Subtask 2 (10%): 1 ≤ N ≤ 50.

Subtask 3 (14%): 1 ≤ N ≤ 300.

Subtask 4 (14%): 1 ≤ N ≤ 2 000.

Subtask 5 (7%): 1 ≤ N ≤ 100 000, B_i = 0.

Subtask 6 (13%): 1 ≤ N ≤ 100 000, Y = 1.

Subtask 7 (12%): 1 ≤ N ≤ 100 000, X + Y = N.

Subtask 8 (11%): 1 ≤ N ≤ 100 000.

Subtask 9 (15%): 1 ≤ N ≤ 500 000.

Subtask 10 (0%): Sample Testcases

Sample Testcase 1

Input

3 1 1
1 3
4 1
5 6

Output

2

Sample Testcase 2

Input

4 2 1
3 4
0 3
4 5
3 10

Output

7