딸기

문제

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

예제 출력 1

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

예제 출력 2

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

예제 출력 3

198