Problem Statement

Just Oishi Ichigo Farm (hereafter JOI Farm) is a strawberry farm famous for being long and narrow from east to west, and its entrance is located at the westernmost point of the farm. Hereafter, the point located $k$ meters east of the entrance is called Point $k$.

Inside JOI Farm, $N$ strawberries are growing. They are numbered from $1$ to $N$. All strawberries are green until time $0$. Strawberry $i$ ($1 \le i \le N$) grows at Point $A_{i}$, and at time $T_{i}$ it ripens and becomes red.

Strawberries cannot be harvested while they are green. In other words, strawberry $i$ cannot be harvested until time $T_{i}$. Starting from the farm entrance at Point $0$ at time $0$, you move in the east-west direction at a maximum speed of $1$ meter per second while harvesting strawberries. The time required to harvest a strawberry can be ignored.

Given the information about the strawberry farm, write a program to find the minimum time required to harvest all strawberries in a red state and return to the entrance.

Constraints

• $1 \le N \le 100\,000$.
• $0 \le A_{i} \le 1\,000\,000\,000 (= 10^{9})$ ($1 \le i \le N$).
• $0 \le T_{i} \le 1\,000\,000\,000 (= 10^{9})$ ($1 \le i \le N$).
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 T_1
A_2 T_2
:
A_N T_N

Output

Output the minimum time required to harvest all strawberries in a red state and return to the entrance on $1$ line.

Sample 1

Input

10
1 3
2 1
3 4
4 1
5 5
6 9
7 2
8 6
9 5
10 3

Output

20

If you spend the first $10$ seconds moving to Point $10$, you can harvest strawberries $2, 4, 5, 7, 8, 9, 10$ in this order along the way. Then, if you spend $10$ seconds returning to Point $0$, you can harvest strawberries $6, 3, 1$ in this order along the way. In this way, all $10$ strawberries can be harvested in a red state.

Sample 2

Input

10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45

Output

450

By moving as follows, you can harvest all strawberries in a red state in $450$ seconds:

1. Spend $45$ seconds moving to Point $45$. Since it is now time $45$, you can harvest strawberry $10$. After harvesting, spend $45$ seconds moving to Point $0$.
2. After that, spend $40$ seconds moving to Point $40$. Since it is now time $130$, you can harvest strawberry $9$. After harvesting, spend $40$ seconds moving to Point $0$.
3. After that, spend $35$ seconds moving to Point $35$. Since it is now time $205$, you can harvest strawberry $8$. After harvesting, spend $35$ seconds moving to Point $0$.
4. After that, spend $30$ seconds moving to Point $30$. Since it is now time $270$, you can harvest strawberry $7$. After harvesting, spend $30$ seconds moving to Point $0$.
5. After that, spend $25$ seconds moving to Point $25$. Since it is now time $325$, you can harvest strawberry $6$. After harvesting, spend $25$ seconds moving to Point $0$.
6. After that, spend $20$ seconds moving to Point $20$. Since it is now time $370$, you can harvest strawberry $5$. After harvesting, spend $20$ seconds moving to Point $0$.
7. After that, spend $15$ seconds moving to Point $15$. Since it is now time $405$, you can harvest strawberry $4$. After harvesting, spend $15$ seconds moving to Point $0$.
8. After that, spend $10$ seconds moving to Point $10$. Since it is now time $430$, you can harvest strawberry $3$. After harvesting, spend $10$ seconds moving to Point $0$.
9. After that, spend $5$ seconds moving to Point $5$. Since it is now time $445$, you can harvest strawberry $2$. After harvesting, spend $5$ seconds moving to Point $0$.
10. You reach Point $0$ at exactly time $450$, so you can harvest strawberry $1$. You arrive at Point $0$ at the same time as you finish harvesting all strawberries.

Sample 3

Input

15
11 23
3 94
89 3
38 58
65 29
41 3
80 42
22 76
48 85
83 98
87 29
97 96
22 75
57 25
99 33

Output

198