Problem B
Road Trip

Tony is going on a road trip. Because gas is so expensive, Tony wants to carefully choose the gas stations he refuels at to save as much money as possible.

For simplicity, assume Tony is driving on a straight road from left to right. There are $n$ gas stations along the road, where each gas station is uniquely identified by its distance to the right of the origin (Tony’s initial position). The cost per gallon of gas may be different at different gas stations. Finally, one gallon of gas allows Tony’s car to travel one kilometer.

When Tony reaches a gas station, he may refuel his car to any amount, as long as the total amount of fuel in his car doesn’t exceed the car’s fuel tank capacity $g$.

Assuming Tony has a full tank initially, what is the minimum cost to travel to the rightmost gas station?

Input

The first line of the input contains two integers $n$ and $g$. It is guaranteed that $1\leq n, g\leq 200\, 000$.

The next $n$ lines contains two integers each. The first integer $d_ i$ is the distance of the gas station to the right of the origin (in kilometers). The second integer $c_ i$ is the cost per gallon of gas. It is guaranteed that $1\leq d_ i\leq 4\cdot 10^{10}$, $1\leq c_ i\leq 10^9$, and that no two gas stations are located at the same point.

Output

If it is possible for Tony to complete his trip without running out of gas, print a single integer $C$, the minimum cost to complete the trip. Otherwise, print “cancel road trip” (without quotes).

3 10
2 100
1 10
11 5

10

3 10
2 100
1 10
13 5

cancel road trip

3 10
10 5
1 1
12 3

6