305124: CF976E. Well played!

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Well played!

题意翻译

【题目描述】 小Y最近沉迷于一款打怪游戏《赛某号》。现在,他正在参加赛某号的春季联赛。 他有n只精灵。每只精灵都有对应的生命值hpi和攻击值di。在比赛过程中,小Y可以借助巴拉拉小魔仙之力,说出这两种咒语: 1、“乌卡拉!血量!加倍!“意即将当前精灵的生命值加倍。 2、“乌卡拉!生命之力!”意即将当前精灵的生命值赋给当前精灵的攻击值。(使得di=hpi) 小Y当然不能无限使用这两种咒语。在一局游戏中,他可以使用第一种咒语a次,第二次咒语b次。由于小Y购买了超级Nono,所以这两种咒语都可以被多次用在同一精灵身上,且咒语的使用顺序没有限制。小Y可以不用完所有的咒语。 小Y非常希望通过使用这些咒语使得自己的精灵战斗群的攻击值达到最大。现在,小Y想知道这个最大值。 【输入格式】 输入第一行包括用空格隔开的三个正整数n,a,b。n,a,b的含义见题目描述。 输入第2行到第n+1行,每行两个整数hp,dmg。第i行表示第i-1个精灵的生命值和攻击值。 【输出格式】 输出一行一个整数,代表小Y的精灵战斗群能达到的最大攻击值。 【样例1解释】 小Y在第二只精灵上先使用第一种魔咒将其生命值加倍,此时的生命值为12。此时,再用第二种魔咒将它的攻击值赋为当前的生命值,则第二只精灵的攻击值为12。可以证明,不存在其它的方案使得这两只精灵的攻击值总和更大。

题目描述

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: 1. Doubles health of the creature ( $ hp_{i} $ := $ hp_{i}·2 $ ); 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 $ .

Input

题意翻译

【题目描述】 小Y最近沉迷于一款打怪游戏《赛某号》。现在,他正在参加赛某号的春季联赛。 他有n只精灵。每只精灵都有对应的生命值hpi和攻击值di。在比赛过程中,小Y可以借助巴拉拉小魔仙之力,说出这两种咒语: 1、“乌卡拉!血量!加倍!“意即将当前精灵的生命值加倍。 2、“乌卡拉!生命之力!”意即将当前精灵的生命值赋给当前精灵的攻击值。(使得di=hpi) 小Y当然不能无限使用这两种咒语。在一局游戏中,他可以使用第一种咒语a次,第二次咒语b次。由于小Y购买了超级Nono,所以这两种咒语都可以被多次用在同一精灵身上,且咒语的使用顺序没有限制。小Y可以不用完所有的咒语。 小Y非常希望通过使用这些咒语使得自己的精灵战斗群的攻击值达到最大。现在,小Y想知道这个最大值。 【输入格式】 输入第一行包括用空格隔开的三个正整数n,a,b。n,a,b的含义见题目描述。 输入第2行到第n+1行,每行两个整数hp,dmg。第i行表示第i-1个精灵的生命值和攻击值。 【输出格式】 输出一行一个整数,代表小Y的精灵战斗群能达到的最大攻击值。 【样例1解释】 小Y在第二只精灵上先使用第一种魔咒将其生命值加倍,此时的生命值为12。此时,再用第二种魔咒将它的攻击值赋为当前的生命值,则第二只精灵的攻击值为12。可以证明,不存在其它的方案使得这两只精灵的攻击值总和更大。

加入题单

上一题 下一题 算法标签: