페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4774

딸기 1초 128MB

문제

긴 도로를 따라 딸기가 심어져 있고 N개의 딸기가 열렸다.

i번 딸기는 도로의 시작점에서 A_i미터 떨어져 있고 T_i초가 지나면 빨갛게 익는다.

당신은 도로의 시작점에서 출발해 모든 딸기를 따고 출발지로 돌아오려 한다.

당신은 1미터를 이동하는데 정확히 1초가 걸린다. ( 이동하지 않고 가만히 기다려도 시간은 흐른다. )

당신은 딸기를 매우 빠르게 따므로 따는데 걸리는 시간은 무시할 수 있다.

하지만 그 어떤 딸기도 익기 전에는, 즉 T_i초가 지나기 전에는 딸 수 없다.

모든 딸기를 따고 돌아오는데 걸리는 최소 시간을 구하자.​ 


입력

첫 줄에 N이 주어진다.

이후 N줄에 걸쳐 i번째 줄에는 A_i, T_i가 차례로 주어진다.

  • 1 \le N \le 100,000

  • 0 \le A_i, T_i \le 1,000,000,000


출력

모든 딸기를 따고 출발지로 돌아오는데 걸리는 최소 시간을 출력하라. 


예제1

입력
10

13

21

34

41

55

69

72

86

95

103
출력
20

예제2

입력
10

0450

5445

10430

15405

20370

25325

30270

35205

40130

4545
출력
450

예제3

입력
15

1123

394

893

3858

6529

413

8042

2276

4885

8398

8729

9796

2275

5725

9933
출력
198

출처

JOI 2020 예선 2

역링크