Problem Description

Just Oishi Ichigo Farm (hereafter JOI Farm) is famous for its long and narrow strawberry farm, with the entrance located at the westernmost point. Hereafter, we will refer to the place $ k $ meters east of the entrance as point $ k $.

Within JOI Farm, there are $ N $ strawberries growing. Each strawberry is numbered from $ 1 $ to $ N $. All strawberries are green until time $ 0 $. Strawberry $ i $ ($1 \leq i \leq N$) grows at point $ A_i $ and turns red at time $ T_i $.

Strawberries cannot be harvested while they are green. That is, strawberry $ i $ cannot be harvested until time $ T_i $. You start at time $ 0 $ at point $ 0 $, the entrance of the farm, and move east or west at a maximum speed of $ 1 $ meter per second while harvesting strawberries. The time it takes to harvest a strawberry is negligible.

Given the information about the strawberry farm, create a program that calculates the minimum time required to harvest all strawberries in their red state and return to the entrance.

Input Format

The input is provided from the standard input in the following format:

$ N $ $ A_1 $ $ T_1 $ $ A_2 $ $ T_2 $ $\vdots$ $ A_N $ $ T_N $

Output Format

Output the minimum time required to harvest all strawberries in their red state and return to the entrance in one line.

Sample Input and Output

Sample Input #1

10
1 3
2 1
3 4
4 1
5 5
6 9
7 2
8 6
9 5
10 3

Sample Output #1

20

Sample Input #2

10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45

Sample Output #2

450

Sample Input #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

Sample Output #3

198

Notes/Hints

Constraints

• $1 \leq N \leq 100,000$.
• $0 \leq A_i \leq 1,000,000,000 (=10^9)$ ($1 \leq i \leq N$).
• $0 \leq T_i \leq 1,000,000,000 (=10^9)$ ($1 \leq i \leq N$).
• All input values are integers.

Sample Explanation 1

By spending the first $ 10 $ seconds moving to point $ 10 $, you can harvest strawberries $ 2, 4, 5, 7, 8, 9, 10 $ in that order. Then, by spending another $ 10 $ seconds returning to point $ 0 $, you can harvest strawberries $ 6, 3, 1 $ in that order. This allows you to harvest all $ 10 $ strawberries in their red state.

Sample Explanation 2

By moving as follows, you can harvest all strawberries in their red state in $ 450 $ seconds:

1. Spend $ 45 $ seconds moving to point $ 45 $. At time $ 45 $, you can harvest strawberry $ 10 $. Then spend $ 45 $ seconds returning to point $ 0 $.
2. Spend $ 40 $ seconds moving to point $ 40 $. At time $ 130 $, you can harvest strawberry $ 9 $. Then spend $ 40 $ seconds returning to point $ 0 $.
3. Spend $ 35 $ seconds moving to point $ 35 $. At time $ 205 $, you can harvest strawberry $ 8 $. Then spend $ 35 $ seconds returning to point $ 0 $.
4. Spend $ 30 $ seconds moving to point $ 30 $. At time $ 270 $, you can harvest strawberry $ 7 $. Then spend $ 30 $ seconds returning to point $ 0 $.
5. Spend $ 25 $ seconds moving to point $ 25 $. At time $ 325 $, you can harvest strawberry $ 6 $. Then spend $ 25 $ seconds returning to point $ 0 $.
6. Spend $ 20 $ seconds moving to point $ 20 $. At time $ 370 $, you can harvest strawberry $ 5 $. Then spend $ 20 $ seconds returning to point $ 0 $.
7. Spend $ 15 $ seconds moving to point $ 15 $. At time $ 405 $, you can harvest strawberry $ 4 $. Then spend $ 15 $ seconds returning to point $ 0 $.
8. Spend $ 10 $ seconds moving to point $ 10 $. At time $ 430 $, you can harvest strawberry $ 3 $. Then spend $ 10 $ seconds returning to point $ 0 $.
9. Spend $ 5 $ seconds moving to point $ 5 $. At time $ 445 $, you can harvest strawberry $ 2 $. Then spend $ 5 $ seconds returning to point $ 0 $.
10. Arrive at point $ 0 $ exactly at time $ 450 $, allowing you to harvest strawberry $ 1 $. You have harvested all strawberries and arrived at point $ 0 $ simultaneously.

见题面 Input 部分

见题面 Output 部分