题目描述

小爱在高速公路上开车，一开始她在坐标 $0$ 点，出发时，她的车辆的起始速度为 $1$。车辆每开出一单位的距离，小爱可以选择保持速度不变，或将速度增加一个单位，或减少一个单位，任何时候，速度不得低于 $1$。

在行进过程中，小爱会遇到 $n$ 个限速点，其中第 $i$ 个限度点的坐标为 $x_i$，限速为 $L_i$，限速的含义是通过这个点时候的速度不能超过 $L_i$。当小爱通过最后一个限度点的时候，她的旅程就结束了。

请计算，小爱在整个路程中，能够达到的最大速度是多少。

输入格式

• 第一行：单个整数表示 $n$。
• 第 $2$ 行到第 $n+1$ 行，每行两个整数表示 $x_i$ 与 $L_i$

输出格式

• 单个整数：表示可以达到的最高速度。

数据范围

• $30\%$ 的数据，$1\leq n\leq 10$，
• $60\%$ 的数据，$1\leq n\leq 5000$，
• $100\%$ 的数据，$1\leq n\leq 300,000$，
• $1\leq x_1\leq x_2\leq\cdots\leq x_n$
• $1\leq L_i\leq 10^9$

样例数据

输入:

4
10 10
20 20
30 20
40 10

输出:

25

说明:

20到30段先提速再降速