페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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

1 3

2 1

3 4

4 1

5 5

6 9

7 2

8 6

9 5

10 3
출력
20

예제2

입력
10

0 450

5 445

10 430

15 405

20 370

25 325

30 270

35 205

40 130

45 45
출력
450

예제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

출처

JOI 2020 예선 2

역링크 공식 문제집만