31728번 - 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_i$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_i$ 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.

입력

Read the following data from the standard input.

$N$ $K$

$H_1$ $C_1$

$H_2$ $C_2$

$\vdots$

$H_N$ $C_N$

출력

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

제한

• 1ドル ≤ N ≤ 300$.
• 1ドル ≤ K ≤ 10^9$
• 0ドル ≤ H_i ≤ 10^9$ (1ドル ≤ i ≤ N$).
• 1ドル ≤ C_i ≤ 10^9$ (1ドル ≤ i ≤ N$).
• Given values are all integers.

서브태스크

힌트

첨부

• ski2.zip