问题描述

Just Oishi Ichigo 农园（以下简称 JOI 农园）是一家东西向狭长而闻名的草莓农园，入口位于农园最西边。在接下来的描述中，我们将把距离入口向东移动 $k$ 米的地方称为地点 $k$。

JOI 农园内有 $N$ 个草莓。每个草莓都有从 $1$ 到 $N$ 的编号。所有草莓在时间 $0$ 之前都是青色的。草莓 $i$ （$1 \leqq i \leqq N$）在地点 $A_i$ 上结实，当时间达到 $T_i$ 时就会成熟并变成红色。

在草莓变成红色之前，它们是不能被收获的。也就是说，草莓 $i$ 必须等到时间 $T_i$ 才能被收获。你从时间 $0$ 出发，位于农园入口的地点 $0$，以最大速度 $1$ 米/秒沿着东西方向移动并采摘草莓。假设采摘草莓所需的时间可以忽略不计。

给定关于草莓农园的信息，请编写一个程序来计算在收获所有草莓并返回入口之前的最短时间。

约束条件

• $1 \leqq N \leqq 100,000$。
• $0 \leqq A_i \leqq 1,000,000,000 (=10^9)$ （$1 \leqq i \leqq N$）。
• $0 \leqq T_i \leqq 1,000,000,000 (=10^9)$ （$1 \leqq i \leqq N$）。
• 所有输入值都是整数。

输入

输入以以下格式从标准输入中给出。

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

输出

输出收获所有草莓并返回入口的最短时间，输出为一行。

示例 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$。成功地同时收获了所有 $10$ 个草莓并返回了入口。

示例 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