Problem Description

Mr. JOI manages a renowned ski resort on the IOI Plateau and has decided to build a new ski resort on the adjacent 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 the \( i \)-th point (\( 1 \leq i \leq N \)) is \( H_i \) meters, and there are no ski slopes connecting any of the points on the plateau. Additionally, each point is equipped with an unused connection facility.

Mr. JOI's goal is to build the KOI Hotel at one of the points on the plateau and then construct some ski slopes connecting each point on the plateau so that people can ski from any point to the hotel. Specifically, Mr. JOI will build the ski resort following these 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. Select one point from 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 a connection facility at point \( i \). The cost of this work is \( C_i \) per operation.

4. For the remaining \( N - 1 \) points excluding the point where the KOI Hotel is located, perform the following construction: Let \( i \) be the point's number. Choose another point \( j \) with a strictly lower altitude and an unused connection facility, and construct 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 connection facility, the goal cannot be achieved.

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

Write a program that, given the information about each point on the KOI Plateau and the cost \( K \) of each embankment work, finds the minimum cost to build the ski resort.

Input Format

Read the following data from the standard input:

• \( N \) \( K \)
• \( H_1 \) \( C_1 \)
• \( H_2 \) \( C_2 \)
• ...
• \( H_N \) \( C_N \)

Output Format

Output a single line, the minimum cost to build the ski resort.

Sample Input and Output

Input Sample #1

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

Output Sample #1

8

Input Sample #2

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

Output Sample #2

100010

Input Sample #3

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

Output Sample #3

108

Notes/Hints

Sample Explanation 1

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

1. Perform embankment work twice at point 1 and once at point 5. The total cost of these embankment works 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 extension work twice at point 2. The total cost of these extension works is \( 1 \times 2 = 2 \). As a result, the number of connection facilities at each point starting from point 1 becomes \( 1, 3, 1, 1, 1 \).
4. Construct 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.

Thus, the cost of building the ski resort is \( 6 + 2 = 8 \). Since it is not possible to build the ski resort for a cost not exceeding 7, the output is 8.

This sample input satisfies the constraints of sub-tasks 3, 4, 5, and 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 sub-tasks 1, 3, 4, 5, and 6.

Sample Explanation 3

This sample input satisfies the constraints of sub-tasks 2, 3, 4, 5, and 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.

Sub-tasks

• (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.

见题面 Input 部分

见题面 Output 部分