PriceFixed

Description:

Input:

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — the number of products.

Each of next $$$n$$$ lines contains a product description. Each description consists of two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i \leq 10^{14}$$$, $$$1 \leq b_i \leq 10^{14}$$$) — the required number of the $$$i$$$-th product and how many products you need to buy to get the discount on the $$$i$$$-th product.

The sum of all $$$a_i$$$ does not exceed $$$10^{14}$$$.

Output:

Output the minimum sum that Lena needs to make all purchases.

Sample Input:

3
3 4
1 3
1 5

Sample Output:

8

Sample Input:

5
2 7
2 8
1 2
2 4
1 8

Sample Output:

12

Note:

In the first example, Lena can purchase the products in the following way:

1. one item of product $$$3$$$ for $$$2$$$ rubles,
2. one item of product $$$1$$$ for $$$2$$$ rubles,
3. one item of product $$$1$$$ for $$$2$$$ rubles,
4. one item of product $$$2$$$ for $$$1$$$ ruble (she can use the discount because $$$3$$$ items are already purchased),
5. one item of product $$$1$$$ for $$$1$$$ ruble (she can use the discount because $$$4$$$ items are already purchased).

In total, she spends $$$8$$$ rubles. It can be proved that it is impossible to spend less.

In the second example Lena can purchase the products in the following way:

1. one item of product $$$1$$$ for $$$2$$$ rubles,
2. two items of product $$$2$$$ for $$$2$$$ rubles for each,
3. one item of product $$$5$$$ for $$$2$$$ rubles,
4. one item of product $$$3$$$ for $$$1$$$ ruble,
5. two items of product $$$4$$$ for $$$1$$$ ruble for each,
6. one item of product $$$1$$$ for $$$1$$$ ruble.

In total, she spends $$$12$$$ rubles.