题目描述

Just Oishi Ichigo 农场（以下简称 JOI 农场）是一座以东西走向狭长而闻名的草莓农场，其入口位于农场的最西端。下文中，将从入口向东前进 $k$ 米的位置称为地点 $k$。

JOI 农场内结有 $N$ 颗草莓，分别编号为 $1$ 到 $N$。所有草莓在时刻 $0$ 之前都是青色的。草莓 $i$（$1 \le i \le N$）结在地点 $A_{i}$，到了时刻 $T_{i}$ 就会成熟并变成红色状态。

草莓在青色状态下不能采摘。也就是说，草莓 $i$ 直到时刻 $T_{i}$ 才能采摘。你在时刻 $0$ 从位于地点 $0$ 的农场入口出发，以最大每秒 $1$ 米的速度沿东西方向移动并采摘草莓。采摘草莓所需的时间可以忽略不计。

给定关于草莓农场的信息，请编写一个程序，求出将所有草莓在红色状态下采摘完毕后返回入口所需时间的最小值。

数据范围

• $1 \le N \le 100\,000$。
• $0 \le A_{i} \le 1\,000\,000\,000 (= 10^{9})$（$1 \le i \le N$）。
• $0 \le T_{i} \le 1\,000\,000\,000 (= 10^{9})$（$1 \le i \le N$）。
• 输入的所有值均为整数。

输入格式

输入从标准输入按以下格式给出：

N
A_1 T_1
A_2 T_2
:
A_N T_N

输出格式

输出 $1$ 行，表示将所有草莓在红色状态下采摘完毕后返回入口所需时间的最小值。

样例 1

输入

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

输出

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

输出

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$。在采摘完全部草莓的同时到达了地点 $0$。

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