$x$ 轴上有 $n$ 条线段。第 $i$ 条线段的长度记为 $l_i$，其起点位置记为 $x_i$，两者均为整数。我们想要在每条线段上打一个结。结的位置也必须是整数。结可以打在线段上的任意位置，且假设线段的长度不会因打结而缩短。你可以假设没有一条线段完全包含在另一条线段内，这意味着不存在两条线段 $T_i$ 和 $T_j$ ($i \neq j$) 满足 $x_j \le x_i$ 且 $x_i + l_i \le x_j + l_j$。

我们想要确定每条线段上结的位置，使得距离最近的两个结之间的距离尽可能大。

例如，下图展示了六条线段上结的位置。结的位置用点表示。所有线段实际上都位于 $x$ 轴上，但为了区分，它们被分开绘制。在图 I.1 中，距离最近的两个结之间的距离为 20。然而，如果我们改变 $T_2$ 上结的位置，如图 I.2 所示，距离最近的两个结之间的距离变为 25，这正是本题所要求的结果。

图 I.1：6 条线段打结的一个示例。

图 I.2：$T_2$ 结的位置改变后的另一个示例。

给定关于 $n$ 条线段的信息，编写一个程序来计算距离最近的两个结之间的最大距离。

输入格式

程序从标准输入读取数据。输入的第一行包含一个整数 $n$ ($2 \le n \le 100,000$)，表示线段的数量。接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ ($0 \le x_i \le 10^9$) 和 $l_i$ ($1 \le l_i \le 10^9$)，分别表示第 $i$ 条线段的起点位置和长度。你可以假设没有一条线段完全包含在另一条线段内，这意味着不存在两条线段 $T_i$ 和 $T_j$ ($i \neq j$) 满足 $x_j \le x_i$ 且 $x_i + l_i \le x_j + l_j$。

输出格式

程序应向标准输出写入数据。输出仅一行，包含一个整数，即距离最近的两个结之间的最大距离。

样例

样例输入 1

6
0 67
127 36
110 23
50 51
100 12
158 17

样例输出 1

25

样例输入 2

6
0 40
10 55
45 28
90 40
83 30
120 30

样例输出 2

30

样例输入 3

3
0 20
40 10
100 20

样例输出 3

50