该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

在 $x$ 轴上有 $n$ 条绳子 $T$。第 $T_i$ 条绳子的长度用整数 $l_i$ 表示，它的起点位置用整数 $x_i$ 表示。Panda 想在每个绳子上打一个结，结的位置必须是整数，同时Panda可以在绳子中的任何点打结，假设绳子的长度不会因为打结而减少。

Panda想要确定每个绳子的绳结的位置，以使最近的两个相邻绳结之间的距离尽可能大。

Input Format

你将会从thread.in中读入数据。

第一行为一个数字 $n$ ，代表了有 $n$ 条绳子。

接下来的 $n$ 行中每行会有两个数字 $x_i$ 和 $l_i$， $x_i$ 表示绳子的起点位置， $l_i$ 表示绳子的长度。

Output Format

你的结果需要输出到thread.out中，输出只有一个数字，即两个相邻结之间的距离的最小值最大为多少。

Sample

【样例1输入】

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

【样例1输出】

25

【样例1解释】

如图所示为六根线的结的位置，结的位置由一个点表示。所有绳子实际上都位于 $x$ 轴上，此处为了便于区分，我们将绳子单独绘制。在图 $I.1$ 中，最近的两个结之间的距离的最小值是 20。

但是如图 $I.2$ 所示，如果我们在不同的位置为 $T_2$ 打结 ，将 $T_2$ 的绳结位置后移，最近的两个结之间的距离的最小值就从原来的 20 变为 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

Hint

绳子的数量 $n$ 满足 $2 \le n \le 10^5$ ，对于每一条绳子，绳子的起点$x_i$ 满足 $0 \le x_i \le 10^9$ ，绳子的长度 $l_i$ 满足 $1\le l_i \le 10^9$ 。

你可以看作任意两条绳子间没有完全重合，这意味着任意两条绳子 $T_i$ 和 $T_j$ （$i \neq j$ ）间拥有关系 $x_j \le x_i$ 且 $x_i + l_i \le x_j + l_j$ 。