题目描述

在一条数轴上有 $N$ 支蜡烛，第 $i$ 支蜡烛长度为 $A_i$，且位于数轴上的 $X_i$ 处。

时刻 $0$ 时，$N$ 支蜡烛都被点燃。一根点燃的蜡烛每过一时刻就会减少 $1$ 的长度。当长度变为 $0$ 时蜡烛将会熄灭。熄灭的蜡烛的长度不会减少。

时刻 $0$ 时，你位于数轴上的 $0$ 处。一时刻中你可以在数轴上左右移动不超过 $1$ 的单位距离。当你到达某支蜡烛所在的位置时，你可以选择熄灭这支蜡烛，熄灭蜡烛的时间忽略不计。如果有多支蜡烛位于同一个位置，你可以一次性熄灭该位置上的所有蜡烛。

求时刻 $10^{100}$ 时最大的蜡烛总长度。

输入格式

第一行给定$N$ ​。 之后 $N$ 行，每行给定两个参数 $X_i$ $A_i$ 。

输出格式

输出一行，表示答案。

样例 #1

样例输入 #1

3
-2 10
3 10
12 10

样例输出 #1

11

样例 #2

样例输入 #2

5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

样例输出 #2

4999999994

提示

数据范围

• $1\ \leq\ N\ \leq\ 300$
• $-10^9\ \leq\ X_i\ \leq\ 10^9$
• $1\ \leq\ A_i\ \leq\ 10^9$