← 返回题目列表

AtCoder · abc219_h

H. 蜡烛

中文机器翻译题面 查看原题

分数: 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位整数。