The problem setter, Mingming, thinks that setting problems for SDOI 2012 was terrifying because he was always being scolded, so he decided to set problems for SDOI 2013 instead.

The children who participated in SDOI 2012 released a large number of zombies, attempting to attack Mingming's house. As a participant in SDOI 2013, you need to protect the problem setter, Mingming.

Zombies approach along a single straight path. You need to place plants in front of Mingming's door to attack the zombies and prevent them from reaching the house.

In the first level, a zombie with $a_1$ health points approaches at a constant speed from a distance of $x_1$ meters from the house, and you place a plant with an attack power of $y_1$ points/second for defense. In the second level, building on the previous level, a new zombie with $a_2$ health points is added to the front of the queue, at a distance of $d$ meters from the next zombie, and the lead zombie approaches from a distance of $x_2$ meters from the house; you then place a new plant with an attack power of $y_2$ points/second. ... In the $n$-th level, there are $n$ zombies in the queue. The distance between any two adjacent zombies is $d$ meters. The lead zombie has $a_n$ health points, the second zombie has $a_{n-1}$ health points, and so on. The lead zombie approaches from a distance of $x_n$ meters from the house, and the rest of the zombies follow the lead zombie simultaneously. You then place a new plant with an attack power of $y_n$ points/second.

Each zombie moves in a straight line at a speed of $1$ meter/second. Since the firing speed of the plants is much faster than the movement speed of the zombies, the travel time of the plant bullets can be ignored. All zombies appear and approach simultaneously; therefore, once a zombie dies, the next zombie immediately begins to take damage from the plant's bullets. The game score depends on the sum of the attack powers of the plants you placed, $\sum_{i=1}^n y_i$. The smaller the sum, the higher the score. To achieve the upper bound of the score, you must place plants with the minimum possible attack power for each level.

As a participant in SDOI 2013, can you protect the problem setter?

Input

The first line contains two space-separated positive integers $n$ and $d$, representing the number of levels and the distance between adjacent zombies, respectively.

The next $n$ lines each contain two space-separated positive integers. The $(i+1)$-th line contains $A_i$ and $X_i$, representing that compared to the previous level, a zombie with $A_i$ health points is added to the front of the queue, and the lead zombie starts approaching from a distance of $X_i$ meters from the house.

Output

A single number, the minimum total sum of plant attack powers over $n$ levels, rounded to the nearest integer.

Examples

Input 1

5 2
3 3
1 1
10 8
4 8
2 3

Output 1

7

Subtasks

For $100\%$ of the data, $1 \leq n \leq 10^5$, $1 \leq d \leq 10^{12}$, $1 \leq x \leq 10^{12}$, $1 \leq a \leq 10^{12}$.