Problem Description

Mr. JOI manages a famous ski resort on the IOI Plateau. He decided to build a new ski resort on the neighboring KOI Plateau to celebrate the 15th anniversary of the ski resort’s opening.

The KOI Plateau has $N$ points, numbered from $1$ to $N$. Currently, the altitude of point $i$ ($1 \leq i \leq N$) is $H_i$ meters, and there are no ski slopes connecting any points on the plateau. Also, each point is equipped with one unused connector facility.

Mr. JOI’s goal is to build the KOI Hotel at one point on the plateau, and then build some ski slopes to connect every point on the plateau so that people can ski from any point to the hotel. More precisely, Mr. JOI will build the ski resort in the following steps:

1. Perform the following embankment work any number of times (possibly zero): choose a point $i$ and increase the altitude of point $i$ by $1$ meter. The cost of this work is $K$ per operation.

2. Choose one point among the $N$ points and build the KOI Hotel there.

3. Perform the following extension work any number of times (possibly zero): choose a point $i$ and build one connector facility at point $i$. The cost of this work is $C_i$ per operation.

4. For each of the remaining $N - 1$ points other than the point where the KOI Hotel is built, do the following construction. Let $i$ be the index of that point. Choose another point $j$ whose altitude is strictly lower, and use one unused connector facility of point $j$ to build a one-way ski slope from point $i$ to point $j$. Note that if there is no point $j$ with a strictly lower altitude and an unused connector facility, then the goal cannot be achieved.

The construction cost of the ski resort is the sum of the costs of the embankment work and the extension work.

Write a program that, given the information of each point on the KOI Plateau and the cost $K$ per embankment operation, finds the minimum cost to build the ski resort.

Input Format

Read the following data from standard input:

• $N$ $K$
• $H_1$ $C_1$
• $H_2$ $C_2$
• ...
• $H_N$ $C_N$

Output Format

Output one line: the minimum cost to build the ski resort.

5 2
0 6
1 1
0 5
2 1
1 2

8

5 100000
0 6
1 1
0 5
2 1
1 2

100010

8 8
0 36
1 47
2 95
0 59
1 54
0 95
1 87
2 92

108

Hint

Sample Explanation 1

For example, the ski resort can be built as follows:

1. Perform the embankment work twice at point $1$, and once at point $5$. The total cost of these embankment operations is $2 \times (2 + 1) = 6$. The altitudes of the points become $2, 1, 0, 2, 2$ meters.
2. Build the KOI Hotel at point $3$.
3. Perform the extension work twice at point $2$. The total cost of these extension operations is $1 \times 2 = 2$. As a result, starting from point $1$, the numbers of connector facilities at each point become $1, 3, 1, 1, 1$.
4. Build $4$ ski slopes: one from point $1$ to point $2$, one from point $2$ to point $3$, one from point $4$ to point $2$, and one from point $5$ to point $2$.

Therefore, the cost to build the ski resort is $6 + 2 = 8$. Since it is impossible to build the ski resort with cost at most $7$, output $8$.

The sample input satisfies the constraints of subtasks $3, 4, 5, 6$.

Sample Explanation 2

The only difference between this sample input and Sample Input 1 is the value of $K$.

This sample input satisfies the constraints of subtasks $1, 3, 4, 5, 6$.

Sample Explanation 3

This sample input satisfies the constraints of subtasks $2, 3, 4, 5, 6$.

Constraints

• $1 \leq N \leq 300$
• $1 \leq K \leq 10^9$
• $0 \leq H_i \leq 10^9$ ($1 \leq i \leq N$)
• $1 \leq C_i \leq 10^9$ ($1 \leq i \leq N$)
• All given values are integers.

Subtasks

• (5 points) $K \geq 100,000$, $H_i \leq 300$, $C_i \leq 100$ ($1 \leq i \leq N$)
• (12 points) $H_1 \leq H_i$, $C_1 \leq C_i$, $H_i \leq 300$ ($1 \leq i \leq N$)
• (9 points) $N \leq 10$, $H_i \leq 10$ ($1 \leq i \leq N$)
• (33 points) $N \leq 40$, $H_i \leq 40$ ($1 \leq i \leq N$)
• (27 points) $H_i \leq 300$ ($1 \leq i \leq N$)
• (14 points) No additional constraints.

Translated by ChatGPT 5