Условие задачи

Ферма Just Oishi Ichigo (далее — ферма JOI) — это клубничная ферма, известная тем, что она узкая и вытянутая с запада на восток, а её вход находится в самой западной точке фермы. Далее место, расположенное в $k$ метрах к востоку от входа, будем называть точкой $k$.

На ферме JOI растёт $N$ ягод клубники. Они пронумерованы от $1$ до $N$. До момента времени $0$ все ягоды зелёные. Ягода $i$ ($1 \le i \le N$) растёт в точке $A_{i}$ и в момент времени $T_{i}$ созревает и становится красной.

Собирать клубнику в зелёном состоянии нельзя. Иными словами, ягоду $i$ нельзя собрать до наступления момента времени $T_{i}$. Вы выходите в момент времени $0$ от входа на ферму, расположенного в точке $0$, и перемещаетесь в направлении запад-восток с максимальной скоростью $1$ метр в секунду, собирая клубнику. Временем, затрачиваемым на сбор самой ягоды, можно пренебречь.

По заданной информации о клубничной ферме напишите программу, которая находит минимальное время, необходимое для того, чтобы собрать всю клубнику в красном состоянии и вернуться ко входу.

Ограничения

• $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$).
• Все входные значения являются целыми числами.

Входные данные

Входные данные подаются из стандартного потока ввода в следующем формате:

N
A_1 T_1
A_2 T_2
:
A_N T_N

Выходные данные

Выведите в $1$ строке минимальное время, необходимое для того, чтобы собрать всю клубнику в красном состоянии и вернуться ко входу.

Пример 1

Входные данные

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

Выходные данные

20

Если за первые $10$ секунд дойти до точки $10$, то по пути можно собрать ягоды $2, 4, 5, 7, 8, 9, 10$ в этом порядке. Затем, потратив $10$ секунд на возвращение в точку $0$, по пути можно собрать ягоды $6, 3, 1$ в этом порядке. Таким образом можно собрать все $10$ ягод клубники в красном состоянии.

Пример 2

Входные данные

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

Выходные данные

450

Если перемещаться следующим образом, можно собрать всю клубнику в красном состоянии за $450$ секунд:

1. За $45$ секунд дойти до точки $45$. Так как в этот момент время равно $45$, можно собрать ягоду $10$. После сбора за $45$ секунд вернуться в точку $0$.
2. Затем за $40$ секунд дойти до точки $40$. Так как в этот момент время равно $130$, можно собрать ягоду $9$. После сбора за $40$ секунд вернуться в точку $0$.
3. Затем за $35$ секунд дойти до точки $35$. Так как в этот момент время равно $205$, можно собрать ягоду $8$. После сбора за $35$ секунд вернуться в точку $0$.
4. Затем за $30$ секунд дойти до точки $30$. Так как в этот момент время равно $270$, можно собрать ягоду $7$. После сбора за $30$ секунд вернуться в точку $0$.
5. Затем за $25$ секунд дойти до точки $25$. Так как в этот момент время равно $325$, можно собрать ягоду $6$. После сбора за $25$ секунд вернуться в точку $0$.
6. Затем за $20$ секунд дойти до точки $20$. Так как в этот момент время равно $370$, можно собрать ягоду $5$. После сбора за $20$ секунд вернуться в точку $0$.
7. Затем за $15$ секунд дойти до точки $15$. Так как в этот момент время равно $405$, можно собрать ягоду $4$. После сбора за $15$ секунд вернуться в точку $0$.
8. Затем за $10$ секунд дойти до точки $10$. Так как в этот момент время равно $430$, можно собрать ягоду $3$. После сбора за $10$ секунд вернуться в точку $0$.
9. Затем за $5$ секунд дойти до точки $5$. Так как в этот момент время равно $445$, можно собрать ягоду $2$. После сбора за $5$ секунд вернуться в точку $0$.
10. Ровно в момент времени $450$ вы окажетесь в точке $0$ и сможете собрать ягоду $1$. Вы вернулись в точку $0$ одновременно с завершением сбора всей клубники.

Пример 3

Входные данные

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

Выходные данные

198