Description

The problem setter Mingming felt that making problems for SDOI2012 was too scary because he would always be blamed, so he made problems again for SDOI2013.

The kids who participated in SDOI2012 released many zombies, trying to attack Mingming’s home. As a contestant of SDOI2013, you need to protect the problem setter Mingming.

Zombies approach along a single straight road. You need to place plants in front of Mingming’s door to attack the zombies, preventing them from reaching the house.

Level 1: a single zombie with HP $a_1$ starts uniformly approaching from $x_1$ meters away, and you place a plant with attack power $y_1$ points/second to defend. Level 2: based on the previous level, add a new zombie with HP $a_2$ to the front of the queue, at distance $d$ from the next zombie, and the front zombie starts uniformly approaching from $x_2$ meters away; you re-place a plant with attack power $y_2$ points/second. ... Level $n$: there are $n$ zombies in total, adjacent zombies are $d$ meters apart, the front zombie has HP $a_n$, the second has HP $a_{n-1}$, and so on. The front zombie starts uniformly approaching from $x_n$ meters away, and the other zombies follow while approaching at the same time. You re-place a plant with attack power $y_n$ points/second.

Each zombie moves in a straight line at speed $1$ m/s. Since the plants’ firing speed is much higher than the zombies’ movement speed, the bullet travel time in the air can be ignored. All zombies appear and start approaching at the same time. Therefore, when one zombie dies, the next zombie immediately starts taking damage from the plant.

The game score depends on the total attack power you place, $\sum \limits _{i=1} ^{n} y_i$. The smaller the sum, the higher the score. To pursue the best possible score, you should place plants with the smallest possible attack power at every level.

As a contestant of SDOI2013, can you protect the problem setter?

Input Format

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

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

Output Format

Output an integer: the minimal total attack power over the $n$ levels, rounded to the nearest integer.

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

7

Hint

Level 1: there is one zombie with HP $3$ at distance $3$ meters from the house, and the minimal plant attack power is $1.00000$.
Level 2: there is one zombie with HP $1$ at $1$ meter and one zombie with HP $3$ at $3$ meters, and the minimal plant attack power is $1.33333$.
Level 3: there is one zombie with HP $10$ at $8$ meters, one with HP $1$ at $10$ meters, and one with HP $3$ at $12$ meters, and the minimal plant attack power is $1.25000$.
Level 4: there is one zombie with HP $4$ at $8$ meters, one with HP $10$ at $10$ meters, one with HP $1$ at $12$ meters, and one with HP $3$ at $14$ meters, and the minimal plant attack power is $1.40000$.
Level 5: there is one zombie with HP $2$ at $3$ meters, one with HP $4$ at $5$ meters, one with HP $10$ at $7$ meters, one with HP $1$ at $9$ meters, and one with HP $3$ at $11$ meters, and the minimal plant attack power is $2.28571$.
The minimal total plant attack power is $7.26905$.

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

Translated by ChatGPT 5