Trapped in the Haybales (Silver)

题目描述

农夫约翰收到了一批共 $N$ 个大型干草捆（$1 \le N \le 100,000$），并将它们放在连接谷仓与他家的一条道路上的不同位置。每个干草捆 $j$ 具有大小 $S_j$，以及一个互不相同的位置 $P_j$ 来表示其在一维道路上的位置。奶牛贝茜当前位于位置 $B$，该位置上没有干草捆。\n\n奶牛贝茜可以在道路上自由移动，甚至可以移动到某个干草捆所在的位置，但她不能穿过这个位置。不过有一个例外：如果她沿同一方向连续奔跑 $D$ 的距离，她会积累足够的速度，撞破并永久清除任何大小严格小于 $D$ 的干草捆。当然，在这样做之后，她可能会打开更多空间，使她能够对其他干草捆发起冲刺并将其清除。\n\nFJ 目前正在给房子和谷仓重新刷漆，并希望确保贝茜无法到达其中任何一个（奶牛和新鲜油漆可不是好组合！）。因此，FJ 希望确保贝茜永远不会撞破最左端或最右端的干草捆，从而使她有效地被困在干草捆之间。FJ 有能力选择一个干草捆并向其添加干草，以帮助把贝茜困住。请帮助他确定需要给某个干草捆增加的最小额外大小，使得贝茜能够一直被困住。

输入格式

第一行输入包含 $N$ 以及贝茜的初始位置 $B$。\n接下来的 $N$ 行每行描述一个干草捆，包含两个整数，分别表示其大小和位置。所有大小和位置都在范围 $1\ldots 10^9$ 之内。

输出格式

输出一个整数，表示 FJ 为防止贝茜逃脱所需添加的最小干草量。如果无法阻止贝茜逃脱，则输出 -1。

5 7\n8 1\n1 4\n3 8\n12 15\n20 20

4

提示

[题目来源：Brian Dean, 2015]

标签: USACO|2015|Silver

来源

USACO|2015|Silver