题目描述
被困在草捆里
【题目描述】
农民约翰收到了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