Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Well played!

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputRecently Max has got himself into popular CCG "BrainStone". As "BrainStone" is a pretty intellectual game, Max has to solve numerous hard problems during the gameplay. Here is one of them:

Max owns *n* creatures, *i*-th of them can be described with two numbers — its health *hp*_{i} and its damage *dmg*_{i}. Max also has two types of spells in stock:

- Doubles health of the creature (
*hp*_{i}:=*hp*_{i}·2); - Assigns value of health of the creature to its damage (
*dmg*_{i}:=*hp*_{i}).

Spell of first type can be used no more than *a* times in total, of the second type — no more than *b* times in total. Spell can be used on a certain creature multiple times. Spells can be used in arbitrary order. It isn't necessary to use all the spells.

Max is really busy preparing for his final exams, so he asks you to determine what is the maximal total damage of all creatures he can achieve if he uses spells in most optimal way.

Input

The first line contains three integers *n*, *a*, *b* (1 ≤ *n* ≤ 2·10^{5}, 0 ≤ *a* ≤ 20, 0 ≤ *b* ≤ 2·10^{5}) — the number of creatures, spells of the first type and spells of the second type, respectively.

The *i*-th of the next *n* lines contain two number *hp*_{i} and *dmg*_{i} (1 ≤ *hp*_{i}, *dmg*_{i} ≤ 10^{9}) — description of the *i*-th creature.

Output

Print single integer — maximum total damage creatures can deal.

Examples

Input

2 1 1

10 15

6 1

Output

27

Input

3 0 3

10 8

7 11

5 2

Output

26

Note

In the first example Max should use the spell of the first type on the second creature, then the spell of the second type on the same creature. Then total damage will be equal to 15 + 6·2 = 27.

In the second example Max should use the spell of the second type on the first creature, then the spell of the second type on the third creature. Total damage will be equal to 10 + 11 + 5 = 26.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 18:34:49 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|