H - Candles
H - 蜡烛
分数：$600$ 分
问题描述
一条无限长的数轴上有 $N$ 根蜡烛。 第 $i$ 根蜡烛在坐标 $X_i$ 处。在时间 $0$，它的长度为 $A_i$，并且点燃。 每分钟，一根点燃的蜡烛的长度减少 $1$。当长度变为 $0$ 时，它熄灭，之后长度不再发生变化。此外，未点燃的蜡烛的长度不会改变。
Takahashi 在时间 $0$ 时位于坐标 $0$ 处。每分钟，他可以移动最多 $1$ 的距离。如果他所在的坐标有蜡烛，他可以把蜡烛吹灭。（如果有多根蜡烛，则可以将它们全部吹灭。）吹灭蜡烛所需的时间可以忽略不计。
找出在时间 $10^{100}$ 分钟之后，Takahashi 最优行动所能造成的剩余蜡烛的最大可能总长度。
约束
- $1 \leq N \leq 300$
- $-10^9 \leq X_i \leq 10^9$
- $1 \leq A_i \leq 10^9$
- 输入中的所有值都为整数。
输入
从标准输入中以如下格式给出：
输出
输出答案。
3
-2 10
3 10
12 10
11
无论Takahashi的行动如何，位于坐标 $12$ 的第三根蜡烛都会在他吹灭它之前熄灭。
对于其他两根蜡烛，如果他在两分钟内到达坐标 $-2$ 吹灭第一根蜡烛，然后在五分钟内到达坐标 $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$ 位整数来表示。