折扣购物

题目描述

$\blue{噜噜}$ 需要在一家商店中购买商品。

商店中共有 $n$ 种商品，每种商品的库存均为无限。所有商品的原价相同，每件商品需要花费 $2$ 元。

对于第 $i$ 种商品，商店设置了一个折扣条件 $b_i$：

• 若 $\blue{噜噜}$ 在购买该件商品之前，已经累计购买了至少 $b_i$ 件商品，则购买第 $i$ 种商品时，每件只需花费 $1$ 元；
• 否则，购买第 $i$ 种商品时，每件需要花费 $2$ 元。

噜噜 至少需要购买第 $i$ 种商品 $a_i$ 件。商品可以按照任意顺序购买，也可以购买超过规定数量的商品。

请你合理安排购买商品的顺序，使完成所有购买要求所花费的总金额最小，并输出这个最小金额。

输入格式

第一行包含一个整数 $n$，表示商品种类数。

接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，分别表示第 $i$ 种商品至少需要购买的数量，以及购买该商品时享受折扣所需的累计购买数量。

输出格式

输出一行一个整数，表示完成所有购买要求所需花费的最小金额。

样例输入 #1

3
3 4
1 3
1 5

样例输出 #1

8

样例输入 #2

5
2 7
2 8
1 2
2 4
1 8

样例输出 #2

12

数据范围与约定

对于 $100\%$ 的数据，保证：$1\le n\le 10^5$,$1\le a_i,b_i\le 10^{14}$,$\sum_{i=1}^{n}a_i\le 10^{14}$。

• 特殊性质 A：保证所有 $b_i=1$。
• 特殊性质 B：保证所有 $a_i=1$。
• 特殊性质 C：保证 $b_1\le b_2\le\cdots\le b_n$。