P3127 [USACO15OPEN] Trapped in the Haybales G

题目描述

Farmer John 收到了一批 $N$ 个大型干草捆（$1 \le N \le 100,000$），并将它们放置在他通往谷仓的道路上的不同位置。不幸的是，他完全忘记了奶牛 Bessie 正在这条路上吃草，她现在可能被困在这些干草捆之间了！每个干草捆 $j$ 有一个大小 $S_j$ 和一个位置 $P_j$，表示它在这条一维道路上的位置。Bessie 可以在道路上自由移动，甚至可以移动到干草捆所在的位置，但她无法穿过这个位置。唯一的例外是，如果她朝同一方向连续移动 $D$ 单位的距离，她将获得足够的速度，能够突破并永久消除任何大小严格小于 $D$ 的干草捆。当然，在突破之后，她可能会打开更多的空间，从而有机会突破其他干草捆，并继续消除它们。

如果 Bessie 最终能够突破最左侧或最右侧的干草捆，她就可以成功逃脱。请计算道路中所有无法逃脱的实数起始位置的总面积。

输入格式

输入的第一行包含 $N$。接下来的 $N$ 行描述每个干草捆，每行包含两个整数，分别表示干草捆的大小和位置，范围均为 $1 \ldots 10^9$。所有位置均不相同。

输出格式

输出一个整数，表示 Bessie 无法逃脱的道路总面积。

输入输出样例 1

5
8 1
1 4
8 8
7 15
4 20

14