分数: 600 点
问题陈述
有 N 无限数线上的蜡烛。 的 i第根蜡烛位于坐标处 X_i。时 0,它的长度为 A_i 并且亮起。 每分钟,点燃的蜡烛的长度减少 1。当长度变为 0,它会烧坏,之后它的长度不会改变。此外,未点燃的蜡烛的长度不会改变。
高桥在坐标处 0 时间 0。每分钟他最多可以移动的距离 1。如果他当前的坐标有蜡烛,他就可以熄灭那根蜡烛。 (如果那里有多支蜡烛,他可以将它们全部熄灭。) 扑灭一支蜡烛所需的时间可以忽略不计。
求剩余蜡烛的最大可能总长度 10^{100} 时间后分钟 0,通过高桥的最佳行动方针实现。
约束
- 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 : 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位整数。