题目描述

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

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

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

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

进行若干次（可以不进行）增高操作：

选择一个点 $i$，将点 $i$ 的海拔增高 $1$ 米，每次操作代价为 $K$。

选择一个点建设 KOI 酒店。

进行若干次（可以不进行）扩展操作：

选择一个点 $i$，在点 $i$ 新建一个连接设施，每次操作代价为 $C_i$。

对于除 KOI 酒店所在点之外的 $N-1$ 个点，各进行一次：

记当前点编号为 $i$。选择海拔高度严格小于 $i$ 的另一点 $j$，并且使用点 $j$ 的一个闲置连接设施（不消耗点 $i$ 的连接设施）修建一条从点 $i$ 到点 $j$ 的单向滑道。若海拔高度严格小于 $i$ 的点均没有闲置连接设施，则无法完成目标。

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

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

输入格式

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

$N K$

$H1$ $C1$ ​ $H2$ $C2$

$​⋮$

$HN$ $CN$ ​

输出格式

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

样例1：

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

8

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

选择点 $1$ 进行两次增高操作、选择点 $5$ 进行一次增高操作，总花费为 $2 \times (2+1) = 6$。此时点 $1, 2, 3, 4, 5$ 的海拔高度依次为 $2, 1, 0, 2, 2$ 米。

在点 $3$ 建造 KOI 酒店。

选择点 $2$ 进行两次扩展操作，总花费为 $1 \times 2 = 2$。此时点 $1, 2, 3, 4, 5$ 的连接设施数量依次为 $1, 3, 1, 1, 1$。

修建 $4$ 条滑道，分别为：从点 $1$ 到点 $2$；从点 $2$ 到点 $3$；从点 $4$ 到点 $2$；从点 $5$ 到点 $2$。

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

样例2：

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

100010

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

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

样例3：

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 \ (1 \le i \le N)$

$1 \le C_i \le 10^9 \ (1 \le i \le N)$

所有输入的数均为整数。

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

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