题目描述

$n$ 名同学站成一排，准备进行一次水枪大战。第 $i$ 名同学的坐标为 $a_i$，其水枪射程为 $b_i$。也就是说，他可以用水枪攻击到 $[a_i-b_i,a_i+b_i]$ 坐标范围内的其他同学。

为了让所有同学都能攻击到左右两侧的同学，你决定给所有人的水枪都安装一个增压器，让每支水枪的射程增加 $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$。