CF976E.Well played!

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Recently 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.

输入格式

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.

输出格式

Print single integer — maximum total damage creatures can deal.

输入输出样例

输入#1
```
2 1 1
10 15
6 1
```
输出#1
```
27
```
输入#2
```
3 0 3
10 8
7 11
5 2
```
输出#2
```
26
```

说明/提示

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$ .

首页