问题描述

有 $N$ 支蜡烛在一条无限的数线上。第 $i$ 支蜡烛位于坐标 $X_i$。在时间 $0$，蜡烛的长度为 $A_i$ 并且被点燃。每分钟，点燃的蜡烛的长度减少 $1$。当长度变为 $0$ 时，蜡烛燃尽，之后它的长度不再发生变化。此外，未点燃的蜡烛的长度不会改变。

高桥在时间 $0$ 位于坐标 $0$。每分钟，他可以移动最多 $1$ 的距离。如果他当前坐标上有一支蜡烛，他可以将其吹灭。（如果那里有多支蜡烛，他可以把所有蜡烛都吹灭。）吹灭一支蜡烛所需的时间可忽略不计。

找出在时间 $10^{100}$ 分钟后，通过高桥的最佳行动方式，剩余的蜡烛的总长度的最大可能值。

约束条件

• $1 \leq N \leq 300$
• $-10^9 \leq X_i \leq 10^9$
• $1 \leq A_i \leq 10^9$
• 输入中所有的值都是整数。

输入

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

$N$ $X_1$ $A_1$ $X_2$ $A_2$ $\vdots$ $X_N$ $A_N$

输出

输出答案。

示例输入 1

3
-2 10
3 10
12 10

示例输出 1

11

第三支蜡烛，位于坐标 $12$，无论高桥的行为如何，都会在高桥吹灭之前燃尽。
对于其他两支蜡烛，如果高桥在两分钟内到达坐标 $-2$ 吹灭第一支蜡烛，然后在五分钟内到达坐标 $3$ 吹灭第二支蜡烛，这两支蜡烛的长度在此后不会再发生变化。剩下的蜡烛的长度分别是 $10-2=8$ 和 $10-2-5=3$，总长度为 $8+3=11$，这是可以实现的最大值。因此，输出 $11$。

示例输入 2

5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

示例输出 2

4999999994

请注意，两支或多支蜡烛可能占据相同的坐标，并且答案可能无法适应 $32$ 位整数。