Trapped in the Haybales (Bronze)

题目描述

农夫约翰收到了一批包含 $N$ 个大干草捆的货物（$1 \le N \le 4000$），并将它们放置在通往谷仓的道路沿线的不同位置。\n不幸的是，他完全忘记了奶牛贝茜正在道路旁吃草，因此她现在可能被这些干草捆困住了！\n每个干草捆 $j$ 有一个大小 $S_j$，以及一个互不相同的位置 $P_j$，表示其在一维道路上的位置。奶牛贝茜从某个没有干草捆的位置出发，并且可以沿道路自由移动，甚至可以移动到某个干草捆所在的位置，但她不能穿过该位置。\n作为例外，如果她沿同一方向连续奔跑 $D$ 单位距离，她就能积累足够的速度，撞破并永久消除任意大小严格小于 $D$ 的干草捆。当然，在这样做之后，她可能会打开更多空间，使她能够继续冲向其他干草捆并消除它们。\n如果贝茜最终能够撞破最左端或最右端的干草捆，她就可以逃到自由之地。请计算道路上所有实数起始位置的总长度，使得贝茜从这些位置出发无法逃脱。\n例如，如果贝茜从位于位置 1 与 5 的干草捆之间出发无法逃脱，那么这段区域的长度为 4，表示她无法逃脱的起始位置范围长度为 4。

输入格式

输入第一行包含 $N$。\n接下来 $N$ 行每行描述一个干草捆，包含两个整数，分别表示其大小和位置，均在范围 $1\ldots 10^9$ 之内。

输出格式

输出一个整数，表示贝茜无法逃脱的道路区域长度。

5\n8 1\n1 4\n8 8\n7 15\n4 20

14

提示

[题目来源：Brian Dean, 2015]

标签: USACO|2015|Bronze

来源

USACO|2015|Bronze