蜡烛

题目描述

无限数轴上有 $N$ 根蜡烛。

第 $i$ 根蜡烛位于坐标 $X_i$。在时间 $0$，它的长度为 $A_i$，且处于点燃状态。

每过一分钟，点燃的蜡烛长度减少 $1$。当长度变为 $0$ 时，蜡烛燃尽，之后其长度不再变化。另外，未点燃的蜡烛长度不变化。

高桥君在时间 $0$ 位于坐标 $0$。每分钟他最多可以移动距离 $1$。如果他所在的坐标处有蜡烛，他可以熄灭那根蜡烛（如果那里有多根蜡烛，他可以全部熄灭）。熄灭蜡烛所需的时间可以忽略不计。

求在高桥君最优的行动方案下，时间 $0$ 后 $10^{100}$ 分钟时剩余蜡烛总长度的最大值。

输入格式

输入按以下格式从标准输入给出：

$N$
$X_1$ $A_1$
$X_2$ $A_2$
$:$
$X_N$ $A_N$

输出格式

输出答案。

样例

3
-2 10
3 10
12 10

11

第三根蜡烛位于坐标 $12$，无论高桥君如何行动，它都会在熄灭之前燃尽。

对于另外两根蜡烛，如果他先花 2 分钟到坐标 $-2$ 熄灭第一根，再花 5 分钟到坐标 $3$ 熄灭第二根，这两根蜡烛的长度此后不再变化。它们剩余的长度分别为 $10-2=8$ 和 $10-2-5=3$，总和为 $8+3=11$，这是可以达到的最大值。因此输出 $11$。

5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

4999999994

注意，可能有多根蜡烛占据同一坐标，且答案可能超出 $32$ 位整数范围。

数据范围

• $1 \le N \le 300$
• $-10^9 \le X_i \le 10^9$
• $1 \le A_i \le 10^9$
• 输入中的所有值均为整数