Migrated from Lutece 2392 藤原货运

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

或许你们不知道，当年秋名山车神藤原拓海退役后找了份货运的工作，把 AE86 遗忘在时代的眼泪中。

拓海只负责公司右侧的货运工作，一天内有 $n$ 批货运任务陆陆续续地来到了拓海的手上，第 $i$ 批货能在第 $a_i$ 时刻从公司中出仓，然后等到拓海来到公司，把货物运输到公司右侧距公司 $b_i$ 个单位长度的位置，送完车上的货物后拓海需要开车回到公司取下一批货物，且拓海可以囤积一段时间的货物再运送出去。

我们设拓海一个单位时间内能跑一个单位长度的距离，问拓海最少需要多长时间就能完成今天全部的货运任务。

Input

第一行，一个整数 $n$ ($1 \leq n \leq 5 \cdot 10^5$)

接下来 $n$ 行，每行两个整数 $a_i, b_i$ ($1\leq a_i,b_i \leq 10^9$)

(输入中的货物数据已按照 $a_i$ 升序排列)

Output

一个整数表示答案，拓海跑完所有任务的最少时间

Samples

3
1 9
2 6
15 6

31

3
1 9
2 6
15 8

33

Resources

2020 UESTC ICPC Training for Dynamic Programming