← 返回题目列表

Codeforces · 976/E

E. 打得好!

中文机器翻译题面 查看原题

最近Max进入了流行的CCG“BrainStone”。由于《BrainStone》是一款相当智力的游戏,Max在游戏过程中要解决无数难题。这是其中之一:

Max拥有n个生物,其中第i个生物可以用两个数字来描述——它的生命值hpi和它的伤害dmgi。 Max 还拥有两种类型的库存法术:

1. 生物生命值加倍 (hpi := hpi·2);
2. 将生物的生命值分配给其伤害(dmgi := hpi)。

第一种法术总共不能使用超过 a 次,第二种法术总共不能超过 b 次。法术可以对某个生物多次使用。法术可以按任意顺序使用。没有必要使用所有咒语。

麦克斯正忙着准备期末考试,所以他要求你确定如果他以最佳方式使用法术,他对所有生物所能造成的最大总伤害是多少。

输入

第一行包含三个整数 n, a, b (1 ≤ n ≤ 2·105, 0 ≤ a ≤ 20, 0 ≤ b ≤ 2·105) — 分别是生物、第一类法术和第二类法术的数量。

接下来 n 行的第 i 行包含两个数字 hpi 和 dmgi (1 ≤ hpi, dmgi ≤ 109) — 第 i 个生物的描述。

输出

打印单个整数 - 生物可以造成的最大总伤害。

示例

输入 #1

2 1 1
10 15
6 1

输出 #1

27

输入 #2

3 0 3
10 8
7 11
5 2

输出 #2

26

注意

在第一个示例中,麦克斯应该对第二个生物使用第一种类型的法术,然后对同一个生物使用第二种类型的法术。那么总伤害将等于 15 + 6·2 = 27。

在第二个示例中,麦克斯应该对第一个生物使用第二种类型的法术,然后对第三个生物使用第二种类型的法术。总伤害等于 10 + 11 + 5 = 26。