Problem Description

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

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 Ai and Bi.

Output

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

Limits

0 ≤ X, Y ≤ N, X + Y ≤ N, 0 ≤ Ai, Bi ≤ 109.

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, Bi = 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