English · Original
Chinese · Translation
Formal · Original
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.
## Input
The first line contains three integers _n_, _a_, _b_ (1 ≤ _n_ ≤ 2·105, 0 ≤ _a_ ≤ 20, 0 ≤ _b_ ≤ 2·105) — 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_ ≤ 109) — description of the _i_\-th creature.
## Output
Print single integer — maximum total damage creatures can deal.
[samples]
## 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.
最近，Max 开始玩流行的卡牌游戏 "BrainStone"。由于 "BrainStone" 是一款非常智力导向的游戏，Max 在游戏过程中必须解决大量难题。以下是其中一道：
Max 拥有 #cf_span[n] 只生物，第 #cf_span[i] 只生物可以用两个数字描述——它的生命值 #cf_span[hpi] 和它的伤害值 #cf_span[dmgi]。Max 还拥有两种类型的法术：
第一种类型的法术总共最多可以使用 #cf_span[a] 次，第二种类型的法术总共最多可以使用 #cf_span[b] 次。每种法术可以对同一个生物多次使用。法术的使用顺序可以任意，且不一定需要使用完所有法术。
Max 正忙于准备期末考试，因此他请你帮他确定：如果以最优方式使用法术，他能获得的所有生物的最大总伤害是多少。
第一行包含三个整数 #cf_span[n], #cf_span[a], #cf_span[b]（#cf_span[1 ≤ n ≤ 2·105], #cf_span[0 ≤ a ≤ 20], #cf_span[0 ≤ b ≤ 2·105]）——分别表示生物数量、第一种法术和第二种法术的数量。
接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[hpi] 和 #cf_span[dmgi]（#cf_span[1 ≤ hpi, dmgi ≤ 109]）——描述第 #cf_span[i] 只生物。
请输出一个整数，表示生物能造成的最大总伤害。
在第一个示例中，Max 应该对第二只生物使用一次第一种法术，然后对该生物再使用一次第二种法术。此时总伤害为 #cf_span[15 + 6·2 = 27]。
在第二个示例中，Max 应该对第一只生物使用一次第二种法术，再对第三只生物使用一次第二种法术。总伤害为 #cf_span[10 + 11 + 5 = 26]。
## Input
第一行包含三个整数 #cf_span[n], #cf_span[a], #cf_span[b]（#cf_span[1 ≤ n ≤ 2·105], #cf_span[0 ≤ a ≤ 20], #cf_span[0 ≤ b ≤ 2·105]）——分别表示生物数量、第一种法术和第二种法术的数量。接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[hpi] 和 #cf_span[dmgi]（#cf_span[1 ≤ hpi, dmgi ≤ 109]）——描述第 #cf_span[i] 只生物。
## Output
请输出一个整数，表示生物能造成的最大总伤害。
[samples]
## Note
在第一个示例中，Max 应该对第二只生物使用一次第一种法术，然后对该生物再使用一次第二种法术。此时总伤害为 #cf_span[15 + 6·2 = 27]。在第二个示例中，Max 应该对第一只生物使用一次第二种法术，再对第三只生物使用一次第二种法术。总伤害为 #cf_span[10 + 11 + 5 = 26]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of creatures.
Let $ a \in \mathbb{Z}_{\geq 0} $ be the maximum number of spells of type 1.
Let $ b \in \mathbb{Z}_{\geq 0} $ be the maximum number of spells of type 2.
For each creature $ i \in \{1, \dots, n\} $:
- Let $ h_i \in \mathbb{Z}^+ $ be its health.
- Let $ d_i \in \mathbb{Z}^+ $ be its base damage.
**Spell Effects**
- **Type 1**: Doubles a creature’s damage. Can be applied at most $ a $ times in total across all creatures.
- **Type 2**: Sets a creature’s health to its damage. Can be applied at most $ b $ times in total across all creatures.
**Constraints**
1. $ 1 \leq n \leq 2 \cdot 10^5 $
2. $ 0 \leq a \leq 20 $
3. $ 0 \leq b \leq 2 \cdot 10^5 $
4. $ 1 \leq h_i, d_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Maximize the total damage of all creatures after applying spells optimally, where each creature’s final damage is:
- $ d_i $ if no spell is applied,
- $ 2d_i $ if only type 1 is applied,
- $ h_i $ if only type 2 is applied,
- $ 2h_i $ if both type 1 and type 2 are applied (in any order).
Let $ x_i \in \{0,1\} $ indicate whether type 1 spell is applied to creature $ i $.
Let $ y_i \in \{0,1\} $ indicate whether type 2 spell is applied to creature $ i $.
Then the final damage of creature $ i $ is:
$$
f_i(x_i, y_i) =
\begin{cases}
d_i & \text{if } x_i = 0, y_i = 0 \\
2d_i & \text{if } x_i = 1, y_i = 0 \\
h_i & \text{if } x_i = 0, y_i = 1 \\
2h_i & \text{if } x_i = 1, y_i = 1
\end{cases}
$$
The objective is to choose $ x_i, y_i \in \{0,1\} $ for all $ i $, such that:
- $ \sum_{i=1}^n x_i \leq a $
- $ \sum_{i=1}^n y_i \leq b $
and $ \sum_{i=1}^n f_i(x_i, y_i) $ is maximized.
API Response (JSON)
{
"problem": {
"name": "E. Well played!",
"description": {
"content": "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 _",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF976E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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:\n\nMax owns _...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "最近，Max 开始玩流行的卡牌游戏 \"BrainStone\"。由于 \"BrainStone\" 是一款非常智力导向的游戏，Max 在游戏过程中必须解决大量难题。以下是其中一道：\n\nMax 拥有 #cf_span[n] 只生物，第 #cf_span[i] 只生物可以用两个数字描述——它的生命值 #cf_span[hpi] 和它的伤害值 #cf_span[dmgi]。Max 还拥有两种类型的法术：\n\n第...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of creatures. \nLet $ a \\in \\mathbb{Z}_{\\geq 0} $ be the maximum number of spells of type 1. \nLet $ b \\in \\mathbb{Z}_{\\geq 0} $ be the maxim...",
"is_translate": false,
"language": "Formal"
}
]
}