Problem E
Even Electricity

A town gets all its electricity from solar power and a dam that provides hydroelectric power. These sources of energy are not always the most reliable, since the amount of sun and water can vary a lot from day to day. Luckily, the dam has a large reservoir that can store water in order to even out the supply of electricity from day to day.

You will be given information about the $n$ coming days. On the $i$’th day, the solar power station generates $s_ i$ units of electricity. At the same time, $w_ i$ units of water will flow into the reservoir. Each unit of water can be converted into one unit of electricity, and you can decide how much you want to convert and how much should be left in the reservoir. However, the reservoir can only hold $r$ units of water, so at the end of the day the amount of water in the reservoir cannot be larger than $r$. In the beginning of the first day the reservoir is empty.

On the first day, there is no water currently stored in the reservoir. At the end of the last day, the dam will undergo maintenance and must be empty. In other words, all the water that flows into the dam during the $n$ days must at some point be converted to electricity.

Let $e_ i$ be the amount of electricity produced on the $i$’th day. Note that $e_ i = s_ i + r_ i$ where $r_ i$ is how much water from the reservoir you converted on the $i$’th day. Your task is to find the minimum possible value of $\max _ i(e_ i) - \min _ i(e_ i)$.

Input

The first line contains two integers $n$ and $r$ ($1 \leq n \leq 10^5$, $1 \leq r \leq 10^9$), the number of days and the amount of water the reservoir can hold.

The following $n$ lines each contain two integers $s_ i$ and $w_ i$ ($0 \leq s_ i, w_ i \leq 10^9$), the amount of electricity generated by the solar power station, and the amount of water that flowed into the reservoir on the $i$’th day.

Output

Output the minimum possible value of $\max _ i(e_ i) - \min _ i(e_ i)$.

3 1
4 2
2 0
5 1

3