C. 塔台超频(tower)

内存限制:256 MiB 时间限制:1000 ms 输入文件: tower.in 输出文件: tower.out
题目类型:传统 评测方式:文本比较

题目描述

在一条笔直的马路上有 n 个塔台,它们被依次标号为 1, 2, \cdots, n ,分别处于距离马路起点 a _ 1, a _ 2, \cdots, a _ n a _ 1 < a _ 2 < \cdots < a _ n )的位置。

每个塔台初始时有一个通讯半径 b _ 1, b _ 2, \cdots, b _ n ,这代表,对于 i 号塔台,其可以与 [a _ i - b _ i, a _ i + b _ i] 范围内的塔台通讯。

需要特别注意,对于两个塔台 A、B,当且仅当 A 塔台的位置处在 B 塔台的通讯范围内,B 塔台才能向 A 塔台传递信号。请注意这里不是「二者的通讯范围重合,即可通讯」。

现在你可以对这些塔台进行超频。具体的,你可以指定一个电压 k ,之后所有塔台都会被加上 k 的电压,通讯半径都会增大 k 。这里的 k 仅可为非负整数。

现在要求你通过超频,使信号可以从 1 号塔台传输到 n 号塔台,路径不限(即,无论如何,只需要让信号从 1 号塔台到达 n 号塔台即可)。但是由于不合理的超频会较严重地磨损塔台,因此你想要尽可能降低超频的电压。

请你计算出,为了达到以上目的,塔台超频需要的最小电压是多少。

输入格式

输入共 n + 1 行。

第一行为一个整数 n ,代表塔台的数量。
接下来 n 行,每行两个整数 a _ i, b _ i ,分别代表各个塔台的位置和初始通讯半径。

输出格式

输出共一行一个整数,代表为了达到目的,塔台超频需要的最小电压。

样例

样例输入 #1

10
2 3
5 0
6 3
7 2
8 0
10 0
13 2
14 4
15 4
18 2

样例输出 #1

3

数据范围与提示

数据规模与约定

对于 50\% 的数据,保证 2 \leq n \leq 10 ^ 3

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

【普及】