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.

3
3 4
1 3
1 5

8

5
2 7
2 8
1 2
2 4
1 8

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.