2024-sp_Ski_2 — JOI JOI_spring
Task type: batch | Time limit: 2 s | Memory limit: 1024 MB | Difficulty: 21
Algorithms: network flow, graph theory, dynamic programming

![](_page_0_Picture_0.jpeg)

## Ski 2

Mr. JOI, who manages a famous ski resort on the IOI Plateau, has decided to commemorate the 15th anniversary of the ski resort's opening by constructing a new ski resort on the adjacent KOI Plateau.

The KOI Plateau has *N* points numbered from 1 to *N*. Currently, the altitude of point *i* (1 ≤ *i* ≤ *N*) is *H<sub>i</sub>* m, and there exist no courses connecting each point on the plateau. Additionally, each point is equipped with one unused connection facility available.

The goal of Mr. JOI is to construct KOI Hotel at one of the *N* points and then construct some courses connecting each point on the plateau so that one can ski down to the hotel from any point. Specifically, Mr. JOI will construct the ski resort according to 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 m. The cost of this work is *K* per operation.
2. Choose a point from the *N* points and construct KOI Hotel there.
3. Perform the following extension work any number of times (possibly zero):
   - Choose a point *i*, and build one connection facility at point *i*. The cost of this work is *C<sub>i</sub>* per operation.
4. For each of the remaining *N* − 1 points excluding the point with KOI Hotel, perform the following construction:
   - Let *i* be the number of the point. Select another point *j* with a strictly lower altitude than point *i*, and use one unused connection facility at point *j* to construct a one-way course from point *i* to point *j*. Note that if there is no point with an unused connection facility and a strictly lower altitude than point *i*, the goal cannot be achieved.

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

Write a program which, given information about each point on the KOI Plateau and the cost *K* per operation of embankment work, finds the minimum cost of constructing the ski resort.

![](_page_1_Picture_0.jpeg)

### Input

Read the following data from the standard input:

```
N K
H1 C1
H2 C2
...
HN CN
```

### Output

Write one line to the standard output. The output should contain the minimum cost of constructing the ski resort.

### Constraints

*   1 ≤ *N* ≤ 300.
*   1 ≤ *K* ≤ 10<sup>9</sup>.
*   0 ≤ *H<sub>i</sub>* ≤ 10<sup>9</sup> (1 ≤ *i* ≤ *N*).
*   1 ≤ *C<sub>i</sub>* ≤ 10<sup>9</sup> (1 ≤ *i* ≤ *N*).
*   Given values are all integers.

### Subtasks

1.  (5 points) *K* ≥ 100000, *H<sub>i</sub>* ≤ 300, *C<sub>i</sub>* ≤ 100 (1 ≤ *i* ≤ *N*).
2.  (12 points) *H*<sub>1</sub> ≤ *H<sub>i</sub>*, *C*<sub>1</sub> ≤ *C<sub>i</sub>*, *H<sub>i</sub>* ≤ 300 (1 ≤ *i* ≤ *N*).
3.  (9 points) *N* ≤ 10, *H<sub>i</sub>* ≤ 10 (1 ≤ *i* ≤ *N*).
4.  (33 points) *N* ≤ 40, *H<sub>i</sub>* ≤ 40 (1 ≤ *i* ≤ *N*).
5.  (27 points) *H<sub>i</sub>* ≤ 300 (1 ≤ *i* ≤ *N*).
6.  (14 points) No additional constraints.

![](_page_2_Picture_0.jpeg)

### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :------------- |
| 5 2          | 8              |
| 0 6          |                |
| 1 1          |                |
| 0 5          |                |
| 2 1          |                |
| 1 2          |                |

For example, the ski resort can be constructed in the following way:

1.  Perform embankment work twice at point 1 and once at point 5. The total cost of these embankment works is 2 × (2 + 1) = 6. As a result, the altitude of each point becomes 2, 1, 0, 2, 2 m starting from point 1.
2.  Construct KOI Hotel at point 3.
3.  Perform extension work twice at point 2. The total cost of these extension works is 1×2 = 2. As a result, the number of connection facilities at each point becomes 1, 3, 1, 1, 1 starting from point 1.
4.  Construct 4 courses: 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.

Here, the cost of constructing the ski resort is 6 + 2 = 8. Since it is impossible to construct the ski resort with a cost of 7 or less, output 8.

This sample input satisfies the constraints of Subtasks 3, 4, 5, 6.

| Sample Input 2 | Sample Output 2 |
| :------------- | :------------- |
| 5 100000     | 100010         |
| 0 6          |                |
| 1 1          |                |
| 0 5          |                |
| 2 1          |                |
| 1 2          |                |

This sample input differs from Sample Input 1 only in the value of *K*.

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

![](_page_3_Picture_0.jpeg)

| Sample Input 3 | Sample Output 3 |
| :------------- | :------------- |
| 8 8          | 108            |
| 0 36         |                |
| 1 47         |                |
| 2 95         |                |
| 0 59         |                |
| 1 54         |                |
| 0 95         |                |
| 1 87         |                |
| 2 92         |                |

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

Starter code: