#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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*≤ 10

_{i}^{9}.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 4 | 22 | 1s | 256MB | Minimum |

2 | 10 | 42 | 1s | 256MB | Minimum |

3 | 14 | 62 | 1s | 256MB | Minimum |

4 | 14 | 82 | 1s | 256MB | Minimum |

5 | 7 | 20 | 1s | 256MB | Minimum |

6 | 13 | 20 | 1s | 256MB | Minimum |

7 | 12 | 20 | 1s | 256MB | Minimum |

8 | 11 | 162 | 1s | 256MB | Minimum |

9 | 15 | 182 | 1s | 256MB | Minimum |

10 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o sale -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512