杰拉尔迪恩的主要步行道绝对笔直,严格从北向南穿过,很长,两个方向都没有人到达过终点。杰拉尔迪恩人随时都喜欢走在这条路上,所以市长要求《先驱报》用几盏聚光灯照亮这条路。聚光灯已经到达某些地方,杰拉德将无法移动它们。每个聚光灯照亮给定长度的路径的特定段,该段的一端是聚光灯的位置,并且可以将其定向以覆盖聚光灯以南或以北的该段。
这条小路包含一座岛上市长的纪念碑,虽然您可以从纪念碑向任意方向行走,但纪念碑南面没有聚光灯。
您将获得聚光灯的位置及其功率。帮助杰拉德引导所有聚光灯,使路径被照亮部分的总长度尽可能长。
输入
第一行包含整数 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