题目描述

瓜皮星球的能源供应都依赖魔法塔发出的能量。在瓜皮星的能源中心，依次分布着 $n$ 座魔法塔，它们沿一条直线分布，坐标分别是 $a_1,a_2,...,a_n$。

第 $i$ 座魔法塔可以向半径 $b_i$ 以内（包括 $b_i$）的其他魔法塔发射魔力波。为了保证能源输送链正常工作，必须保证每一座魔法塔发射的魔力波能够至少到达它右侧相邻的魔法塔。即：第 $i$ 座魔法塔发射的魔力波必须要能够到达第 $i+1$ 座魔法塔。

你可以使用一颗魔法水晶，使得所有魔法塔的魔力波发射半径增加 $k$。求能够保证能源输送链正常工作所需的 $k$ 的最小值。

输入格式

第一行：输入一个整数 $n$，代表魔法塔的数量。
接下来 $n$ 行：每行输入两个整数 $a _ i, b _ i$，分别代表各个魔法塔的位置和魔力波发射半径。

输出格式

输出一个整数，代表魔力波增加半径的最小值。

样例

5
0 4
2 2
3 1
12 8
19 2

8

数据规模与约定

对于 $100\%$ 的数据，保证 $2 \leq n \leq 5 \times 10 ^ 5$，$0 \leq a _ i, b _ i \leq 10 ^ 9$。