Page not loading? Try clicking here.
Placeholder

#2157

[중등부] 2024 KOI 1차대회 대비 모의고사 (4주차)

딸기 1s 128MB

Problems

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

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

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

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

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

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

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


Input

첫 줄에 N이 주어진다.

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

  • 1 \le N \le 100,000

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


Output

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


Example #1

10

1 3

2 1

3 4

4 1

5 5

6 9

7 2

8 6

9 5

10 3
20

Example #2

10

0 450

5 445

10 430

15 405

20 370

25 325

30 270

35 205

40 130

45 45
450

Example #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
You must sign in to write code.