Somewhere not on Earth there is an infinitely long one-dimensional street with food trucks. If two food trucks are at distance smaller than \(d\) from each other then people get confused and don't know which one to choose. To avoid this problem, the food trucks can move along the street (left or right) at 1 meter per second.

Given the starting positions of the food trucks, you need to find the minimum time needed for each pair of food trucks to be separated by at least \(d\) meters assuming that all of them make optimal movement decisions.

Input

The first line contains two integers \(k\) and \(d\) giving the number of positions containing food trucks and the minimum distance we want to have between any two food trucks, respectively.

The follow \(k\) lines each with two integers \(x\) and \(f\) giving that there are \(f\) food trucks at position \(x\).

Constraints

• \(1 \leq d \leq 10^6\)
• \(1 \leq k \leq 200\)
• \(-10^5 \leq x \leq 10^5\)
• \(1 \leq f \leq 10^6\)

Output

One line with the minimum amount of time it will take for the vendors to spread out apart on the street.

The answer should be accurate up to \(10^{-6}\) relative or absolute precision.

Do not worry about formating the output with printf or others, as long as the precision is ok, your answer will be accepted

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2