题目描述

题目译自 JOISC 2024 Day1 T3 「スキー 2 / Ski 2」

JOI 先生经营了 IOI 高地的一家知名滑雪场。他决定在相邻的 KOI 高地新建一家滑雪场，以纪念开张 15 周年。

KOI 高地有 $N$ 个点，依次从 $1$ 到 $N$ 标号。当前，点 $i\enspace (1\le i\le N)$ 的海拔高度为 $H_i$ 米，且点与点之间还没有任何滑道。此外，每个点各有一个闲置的连接设施。

JOI 先生想要将 KOI 酒店建在 $N$ 个点之一，并且在若干点对之间建设一些滑道，使得从任何一点出发均可以直接通过滑道到达酒店，具体而言，JOI 先生希望按如下步骤建设：

1. 进行若干次（可以不进行）增高操作：
   • 选择一个点 $i$ ，将点 $i$ 的海拔增高 $1$ 米，每次操作代价为 $K$。
2. 选择一个点建设 KOI 酒店。
3. 进行若干次（可以不进行）扩展操作：
   • 选择一个点 $i$，在点 $i$ 新建一个连接设施，每次操作代价为 $C_i$。
4. 对于除 KOI 酒店所在点之外的 $N-1$ 个点，各进行一次：
   • 记当前点编号为 $i$。选择海拔高度严格小于 $i$ 的另一点 $j$，并且使用点 $j$ 的一个闲置连接设施（不消耗点 $i$ 的连接设施）修建一条从点 $i$ 到点 $j$ 的单向滑道。若海拔高度严格小于 $i$ 的点均没有闲置连接设施，则无法完成目标。

建设的总花费是所有进行的增高操作和扩展操作的花费之和。

给定 KOI 高地的每个点和每次增高操作的花费 $K$，求出建设总花费的最小值。

输入格式

从标准输入读入以下内容：

$$\begin{align} & N\enspace K \\ & H_1\enspace C_1 \\ & H_2\enspace C_2 \\ & \vdots \\ & H_n\enspace C_n \end{align} $$

输出格式

一行一个整数，表示满足要求的滑雪场建设花费的最小值。

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

8

以下是一个合法的建设方案：

1. 选择点 $1$ 进行两次增高操作、选择点 $5$ 进行一次增高操作，总花费为 $2\times (2+1)\,=\,6$。此时点 $1,\,2,\,3,\,4,\,5$ 的海拔高度依次为 $2,\,1,\,0,\,2,\,2$ 米。
2. 在点 $3$ 建造 KOI 酒店。
3. 选择点 $2$ 进行两次扩展操作，总花费为 $1\times 2\,=\,2$。此时点 $1,\,2,\,3,\,4,\,5$ 的连接设施数量依次为 $1,\,3,\,1,\,1,\,1$。
4. 修建 $4$ 条滑道，分别为：从点 $1$ 到点 $2$；从点 $2$ 到点 $3$；从点 $4$ 到点 $2$；从点 $5$ 到点 $2$。

这组样例满足子任务 $3,\,4,\,5,\,6$ 的限制。

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

100010

该样例和样例 1 只有 $K$ 的值不同。

这组样例满足子任务 $1,\,3,\,4,\,5,\,6$ 的限制。

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

108

这组样例满足子任务 $2,\,3,\,4,\,5,\,6$ 的限制。

数据范围与提示

对于所有数据，满足：

• $1\le N\le 300$
• $1\le K\le 10^9$
• $0\le H_i\le 10^9\enspace (1\le i\le N)$
• $1\le C_i\le 10^9\enspace (1\le i\le N)$
• 所有输入的数均为整数。

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
$1$	$K\ge 100\,000,\enspace H_i\le 300,\enspace C_i\le 100\enspace (1\le i\le N)$	$5$
$2$	$H_1\le H_i,\enspace C_1\le C_i,\enspace H_i\le 300\enspace (1\le i\le N)$	$12$
$3$	$N\le 10,\enspace H_i\le 10\enspace (1\le i\le N)$	$9$
$4$	$N\le 40,\enspace H_i\le 40\enspace (1\le i\le N)$	$33$
$5$	$H_i\le 300\enspace (1\le i\le N)$	$27$
$6$	无附加限制	$14$