Little D is preparing for a trip around the world. Before departure, he needs to complete $n$ supply preparation operations on his checklist as planned, which are initially numbered $1, 2, \dots, n$ in order.

Let the current quantity of supplies be an integer $x$, with $x = 0$ initially. The $i$-th operation is described by two positive integers $a_i, b_i$. When this operation is executed, the following changes occur in order:

1. First, increase $x$ by $a_i$ (i.e., set $x \leftarrow x + a_i$);
2. Next, check the value of $x$: if $x > b_i$ at this moment, reduce $x$ to $b_i$ (i.e., set $x \leftarrow \min(x, b_i)$).

Before starting to execute the operations, Little D may perform at most one adjustment to the checklist order: choose any one operation, remove it, and move it to the end of the sequence, while the relative order of the remaining operations remains unchanged (he may also choose to make no adjustment at all).

After the adjustment is finished, Little D will execute all $n$ operations in the new order from front to back, executing each operation exactly once. Little D wants to know: after all operations are executed, what is the maximum possible quantity of supplies $x$?

Input

Read data from stdin.

The first line contains a positive integer $n$, representing the number of operations.

The next $n$ lines each contain two positive integers $a_i, b_i$ on the $i$-th line, describing the parameters of the $i$-th operation.

Output

Write to stdout.

Output a single line containing one integer, representing the maximum possible value of the supply quantity $x$ after all operations are executed.

Examples

Input 1

3
1 100
100 90
1 1

Output 1

90

Note

Move the $2$-nd operation to the end of the sequence, so the execution order of the operations becomes $1, 3, 2$. After each operation is executed, the value of $x$ becomes $1, 1, 90$ in turn.

If the $1$-st operation is moved to the end, the final value is $x = 2$; if the order is not adjusted or the $3$-rd operation is moved to the end, the final value is $x = 1$. Therefore, the maximum possible value of $x$ is $90$.

Example 2

See supply/supply2.in and supply/supply2.ans in the contestant directory.

This example satisfies the constraints of test cases $1 \sim 4$.

Example 3

See supply/supply3.in and supply/supply3.ans in the contestant directory.

This example satisfies the constraints of test cases $5 \sim 6$.

Example 4

See supply/supply4.in and supply/supply4.ans in the contestant directory.

This example satisfies the constraints of test cases $7 \sim 10$.

Constraints

For all data, it is guaranteed that $1 \le n \le 2 \times 10^5$ and $1 \le a_i, b_i \le 10^9$. Please note: the data does not guarantee $a_i \le b_i$.

This problem has $10$ test cases in total, each worth $10$ points, and each test case is scored independently. Detailed constraints are shown in the table below.

Special Property A: $b_1 = b_2 = \dots = b_n$.