← 返回题目列表

Codeforces · 1539/D

D. 价格固定

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

莉娜是莫斯科最经济的女孩。因此,当她爸爸让她买一些去乡下旅行的食物时,她去了最好的商店——“PriceFixed”。以下是该店的一些规则:

- 商店中的每种产品都有无限数量的商品。
- 所有产品的价格相同:每件 $$$2$$$ 卢布。
- 对于每件产品$$$i$$$,有经验的买家都有折扣:如果您购买$$$b_i$$$产品(任何类型,不一定类型$$$i$$$),那么对于所有未来购买第$$$i$$$产品,都会有$$$50\%$$$折扣(因此您可以购买第$$$i$$$产品的产品) $$$1$$$卢布!)。

Lena 需要购买 $$$n$$$ 产品:她必须购买第 $$$i$$$ 个产品中的至少 $$$a_i$$$ 商品。帮助莉娜计算如果她选择最佳的购买顺序,她需要花费的最低金额。请注意,如果她愿意,她可以购买超出所需数量的某些产品。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — 产品数量。

接下来的 $$$n$$$ 行中的每一行都包含产品描述。每个描述由两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i \leq 10^{14}$$$, $$$1 \leq b_i \leq 10^{14}$$$) — 第 $$$i$$$ 个产品所需的数量以及您需要购买多少个产品才能获得第 $$$i$$$ 的折扣产品。

所有$$$a_i$$$ 的总和不超过$$$10^{14}$$$。

输出

输出 Lena 进行所有购买所需的最低金额。

示例

输入 #1

3
3 4
1 3
1 5

输出 #1

8

输入 #2

5
2 7
2 8
1 2
2 4
1 8

输出 #2

12

注意

在第一个示例中,Lena 可以通过以下方式购买产品:

1. 一件产品 $$$3$$$ 价格为 $$$2$$$ 卢布,
2. 一件产品 $$$1$$$ 价格为 $$$2$$$ 卢布,
3. 一件产品 $$$1$$$ 价格为 $$$2$$$ 卢布,
4. 一件产品 $$$2$$$ 价格为 $$$1$$$ 卢布(她可以使用折扣,因为已经购买了 $$$3$$$ 商品),
5. 一件产品 $$$1$$$ 价格为 $$$1$$$ 卢布(她可以使用折扣,因为已经购买了 $$$4$$$ 商品)。

她总共花费了 $$$8$$$ 卢布。事实证明,少花钱是不可能的。

在第二个示例中,Lena 可以通过以下方式购买产品:

1. 一件产品 $$$1$$$ 价格为 $$$2$$$ 卢布,
2. 两件产品 $$$2$$$,每件价值 $$$2$$$ 卢布,
3. 一件产品 $$$5$$$ 价格为 $$$2$$$ 卢布,
4. 一件产品 $$$3$$$ 价格为 $$$1$$$ 卢布,
5. 两件产品 $$$4$$$,每件价值 $$$1$$$ 卢布,
6. 一件产品 $$$1$$$,价格为 $$$1$$$ 卢布。

她总共花费了 $$$12$$$ 卢布。