在一条笔直的马路上有 n 个塔台，它们被依次标号为 1, 2, ..., n，分别处于距离马路起点 a 1, a2, ..., an（a1 < a2 < ... < an）的位置。

每个塔台初始时有一个通讯半径 b1, b2, ..., bn，这代表，对于 i 号塔台，其可以与 [ai - bi, ai + bi] 范围内的塔台通讯。

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

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

现在要求你通过超频，使信号可以从 1 号塔台依次通过 2, 3, ... 号塔台传输到 n 号塔台，但是由于不合理的超频会较严重地磨损塔台，因此你想要尽可能降低超频的电压。

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

输入共 n + 1 行。

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

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

提示

数据规模与约定

对于 100% 的数据，保证 2 <= n <= 5 * 10 ^ 5，0 <= ai, bi <= 10 ^ 9。

数组