CF1539D PriceFixed

Lena 是莫斯科最节俭的女孩。因此，当她的父亲让她为去乡下旅行买些食物时，她选择了最好的商店——“PriceFixed”。该商店有如下规则： - 商店中每种商品都有无限多的库存。 - 所有商品的价格相同：每件商品 2 卢布。 - 对于每种商品 $i$，有一个针对老顾客的折扣：如果你已经购买了 $b_i$ 件商品（任意种类的商品均可，不一定是第 $i$ 种），那么从此以后购买第 $i$ 种商品时都可以享受 50% 的折扣（即每件第 $i$ 种商品只需 1 卢布）。 Lena 需要购买 $n$ 种商品：她必须至少购买第 $i$ 种商品 $a_i$ 件。请帮助 Lena 计算，在最优购买顺序下，她至少需要花多少钱。注意，如果她愿意，她可以购买某些商品超过所需数量。

第一行包含一个整数 $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$ 种商品需要购买的数量，以及获得该商品折扣所需的累计购买商品总数。 所有 $a_i$ 的和不超过 $10^{14}$。

输出 Lena 完成所有购买所需花费的最小金额。

在第一个样例中，Lena 可以按如下顺序购买商品： 1. 购买 1 件第 3 种商品，花费 2 卢布； 2. 购买 1 件第 1 种商品，花费 2 卢布； 3. 再购买 1 件第 1 种商品，花费 2 卢布； 4. 购买 1 件第 2 种商品，此时已累计购买 3 件商品，可以享受折扣，花费 1 卢布； 5. 再购买 1 件第 1 种商品，此时已累计购买 4 件商品，可以享受折扣，花费 1 卢布。 总共花费 8 卢布。可以证明无法花费更少。 在第二个样例中，Lena 可以按如下顺序购买商品： 1. 购买 1 件第 1 种商品，花费 2 卢布； 2. 购买 2 件第 2 种商品，每件 2 卢布，共 4 卢布； 3. 购买 1 件第 5 种商品，花费 2 卢布； 4. 购买 1 件第 3 种商品，此时已累计购买 4 件商品，可以享受折扣，花费 1 卢布； 5. 购买 2 件第 4 种商品，此时已累计购买 5 件商品，可以享受折扣，每件 1 卢布，共 2 卢布； 6. 再购买 1 件第 1 种商品，此时已累计购买 7 件商品，可以享受折扣，花费 1 卢布。 总共花费 12 卢布。 由 ChatGPT 4.1 翻译