最近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。