Farmer John has received a shipment of N large hay bales (1 <= N <= 100,000), and placed them at various locations along the road. Each bale j has a size S_j and a distinct position P_j along the one-dimensional road. Bessie the cow is currently located at position B, where there is no hay bale.

Bessie can move freely along the road up to the position of a bale, but cannot cross through it. As an exception, if she runs in the same direction for D units of distance, she builds up enough speed to break through and permanently eliminate any hay bale of size strictly less than D.

FJ wants to make sure Bessie never breaks through the leftmost or rightmost bale, so she stays trapped. FJ can add hay to a single bale of his choosing. Please help him determine the minimum amount of extra size he needs to add to some bale to ensure Bessie stays trapped.

Line 1: N and Bessie's initial position B. Each of the next N lines describes a bale with two integers: its size and position. All sizes and positions are in the range 1...10^9.

A single integer giving the minimum amount of hay FJ needs to add to prevent Bessie from escaping. Print -1 if it is impossible to prevent her escape.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > US Open > Silver