The Flowerpot Watering Problem

Farmer John is having trouble watering his plants. His drops of rain fall from the clouds at a constant speed of \(1\) unit per second. You are given \(N\) raindrops. Each raindrop is represented by its horizontal coordinate \(x\) and its height \(y\) in the 2D plane. Since the drop falls directly downward, it will hit the \(x\)-axis at time \(y\) seconds.

You want to place a flowerpot of width \(W\) somewhere along the \(x\)-axis. The pot, if positioned over an interval \([L, L+W]\), will catch every raindrop that lands within that interval (drops landing exactly on either edge are counted). The objective is to ensure that the time difference between the first raindrop to hit the pot and the last raindrop to hit it is at least \(D\) seconds; in other words, if the earliest drop caught falls at time \(y_{min}\) and the latest at \(y_{max}\), then \(y_{max} - y_{min} \ge D\).

Your task is to find the minimum possible width \(W\) such that there exists a placement of the pot that catches at least two drops whose landing times differ by at least \(D\) seconds. Note that the optimal pot can be imagined as snugly covering a pair (or more) of raindrops whose horizontal distance determines the minimum required width.

Mathematically, if a raindrop lands at coordinate \((x, y)\), then it impacts the ground at time \(y\). For a chosen pot placement spanning from \(L\) to \(L+W\), let \(S\) be the set of all raindrops such that \(L \le x \le L+W\). You require that \(\max_{(x,y) \in S}y - \min_{(x,y) \in S}y \ge D\). Determine the minimum \(W\) for which such an interval exists.

inputFormat

The first line contains two integers \(N\) and \(D\) (with \(1 \le N \le 100{,}000\) and \(D \ge 0\)). Each of the following \(N\) lines contains two integers representing \(x\) and \(y\): the horizontal coordinate and the height (which is equal to the landing time) of a raindrop.

outputFormat

Output a single integer: the minimum width \(W\) of the flowerpot that can be placed so that the difference between the landing times of the first and the last raindrop caught is at least \(D\) seconds.

sample

3 2
1 3
4 1
2 5

1