문제 설명

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