问题6831--被困在草捆里

6831: 被困在草捆里

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

被困在草捆

【题目描述】

农民约翰收到了N个大干草捆(1≤N≤4000),并将它们放置在通往谷仓道路沿线的不同位置。不幸的是,他完全忘记了奶牛贝茜正在路边吃草,她现在可能被困在草捆里了!

每个包j都有一个大小Sj和一个明确的位置Pj,给出其沿一维道路的位置。奶牛贝西从一个没有干草捆的地方出发,它可以沿着路自由地移动,甚至可以走到有干草捆的地方,但是它不能穿过这个地方。作为一个例外,如果她在同一个方向上跑了D单位的距离,她建立足够的速度来突破并永久消除任何尺寸严格小于D的干草堆。当然,在这样做之后,她可能会打开更多的空间,让她跑到其他干草堆上,也消除它们。

如果贝西最终能突破最左边或最右边的干草堆,她就能逃到自由的地方。请计算由贝西无法逃脱的实起始位置组成的道路总面积。例如,如果贝西从1号和5号位置的干草堆中间开始就无法逃脱,那么这些干草堆就会包围一个4号大小的区域,贝西无法逃脱。

输入格式】(trapped.in):

第一行输入包含N,接下来的N行中每一行描述一个捆,并包含两个整数,给出它的大小和位置,每个整数的范围为1…109

输出格式】(trapped.out):

输出一个整数,给出贝茜无法逃脱的道路面积。

样例输入】:

5

8 1

1 4

8 8

7 15

4 20

样例输出】:

14

 

来源/分类