返回小组 开始 2021-07-28 08:00:00

202107第三轮测试(J)

结束 2021-07-28 12:00:00
Contest is over.
当前 2024-09-20 01:02:48

C. 重叠的线段

描述

给你很多段线段,每段线段都有一个起始点si和和长度li。如果两段线段有部分重叠,则称这两段线段相互覆盖。比如si=4,li=4,sj=5,lj=5,第i段线段的覆盖区间为[4,8],第j段线段的覆盖区间为[5,10],二者可以连接成[4,10]的线段。再比如si=4,li=2,sj=7,lj=3,第i和j段线段覆盖区间分别为[4,6]、[7,10],两个区间是分隔开的。

现在给定一组线段,问最大的覆盖区间有多大?

输入

第一张为一个正整数n,表示有n段线段。 第2至n+1行,每行为两个正整数si和li,表示第i段线段的起始点和长度。

输出

最大(长)覆盖区间。

样例

输入

3
4 4
5 5
1 2

输出

6

输入

2
4 2
7 3

输出

3

提示

对100%的数据,1≤n≤100,0≤si,li≤100000。


Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交