Hay Bale Trapping

Farmer John has received a shipment of \(N\) large hay bales (\(1 \le N \le 100{,}000\)), placed at distinct positions along a one‐dimensional road. Bale \(j\) is at position \(P_j\) and has size \(S_j\). Bessie the cow is initially at position \(B\) (where there is no bale). Bessie may move freely within the region that is not blocked by a hay bale; however, she cannot cross a bale’s location unless she builds up enough momentum. In particular, if she runs continuously for a distance \(D\) in one direction, she can break through and permanently eliminate any hay bale whose size is strictly less than \(D\) (i.e. if \(S_j < D\)). When a bale is broken the region Bessie can run in becomes larger, and she may use this new space to break additional hay bales.

Farmer John wants to keep Bessie safely trapped between two extreme (leftmost and rightmost) hay bales – he does not want her to break through either extreme. To help, he is allowed to add extra hay to one bale of his choosing, thereby increasing its size. Your task is to determine the minimum extra hay that must be added (to one bale only) so that no matter what running strategy Bessie uses, she is never able to break through either the leftmost or rightmost bale.

Note: All formulas are given in \(\LaTeX\) format. In particular, a bale \(j\) breaks if Bessie can run a distance \(D\) satisfying \[ D > S_j \] when she attacks it. The extra hay added to the chosen bale increases its size by the added amount.

inputFormat

The first line contains two integers \(N\) and \(B\) (the number of hay bales and Bessie’s starting position). The next \(N\) lines each contain two integers \(P_j\) and \(S_j\) representing the position and size of bale \(j\). It is guaranteed that all \(P_j\) are distinct. You may assume that \(B\) lies strictly between the leftmost and rightmost hay bales.

outputFormat

Output a single integer: the minimum extra hay size that must be added to one bale in order to keep Bessie trapped so that she never breaks through the leftmost or rightmost bale.

sample

3 5
2 10
7 10
9 10

0