題目描述

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