← 返回题目列表

Codeforces · 559/E

E. 杰拉尔德和路径

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

杰拉尔迪恩的主要步行道绝对笔直,严格从北向南穿过,很长,两个方向都没有人到达过终点。杰拉尔迪恩人随时都喜欢走在这条路上,所以市长要求《先驱报》用几盏聚光灯照亮这条路。聚光灯已经到达某些地方,杰拉德将无法移动它们。每个聚光灯照亮给定长度的路径的特定段,该段的一端是聚光灯的位置,并且可以将其定向以覆盖聚光灯以南或以北的该段。

这条小路包含一座岛上市长的纪念碑,虽然您可以从纪念碑向任意方向行走,但纪念碑南面没有聚光灯。

您将获得聚光灯的位置及其功率。帮助杰拉德引导所有聚光灯,使路径被照亮部分的总长度尽可能长。

输入

第一行包含整数 n (1 ≤ n ≤ 100) — 聚光灯的数量。 n 行中的每一行包含两个空格分隔的整数 ai 和 li (0 ≤ ai ≤ 108, 1 ≤ li ≤ 108)。数字 ai 表示第 i 个聚光灯向北有多远,数字 li 表示它照亮的线段的长度。

保证所有的ai都是不同的。

输出

打印单个整数 — 路径被照亮部分的最大总长度。

示例

输入 #1

3
1 1
2 2
3 3

输出 #1

5

输入 #2

4
1 2
3 3
4 3
6 2

输出 #2

9