管理 IOI 高原著名滑雪场的 JOI 先生，为了纪念滑雪场开业 15 周年，决定在邻近的 KOI 高原上建造一个新的滑雪场。

KOI 高原上有 $N$ 个点，编号从 $1$ 到 $N$。目前，点 $i$ ($1 \le i \le N$) 的海拔为 $H_i$ 米，高原上各点之间没有任何滑雪道。此外，每个点最初都配备有一个未使用的连接设施。

JOI 先生的目标是在这 $N$ 个点中的某一点建造 KOI 酒店，并建造一些连接高原上各点的滑雪道，使得从任何一点都可以滑雪到达酒店。具体来说，JOI 先生将按照以下步骤建造滑雪场：

1. 执行任意次数（可能为零）的路基工程：
   • 选择一个点 $i$，将点 $i$ 的海拔增加 $1$ 米。每次操作的成本为 $K$。
2. 从 $N$ 个点中选择一个点，并在该处建造 KOI 酒店。
3. 执行任意次数（可能为零）的扩建工程：
   • 选择一个点 $i$，在点 $i$ 处建造一个连接设施。每次操作的成本为 $C_i$。
4. 对于除建有 KOI 酒店的点之外的其余 $N - 1$ 个点，执行以下施工：
   • 设该点编号为 $i$。选择另一个海拔严格低于点 $i$ 的点 $j$，并使用点 $j$ 处的一个未使用连接设施，建造一条从点 $i$ 到点 $j$ 的单向滑雪道。注意，如果不存在海拔严格低于点 $i$ 且拥有未使用连接设施的点，则无法实现目标。

滑雪场的建设成本为所执行的路基工程成本与扩建工程成本之和。

给定 KOI 高原上每个点的信息以及路基工程每次操作的成本 $K$，请编写一个程序，计算建设滑雪场的最小成本。

输入格式

从标准输入读取以下数据：

$N \ K$ $H_1 \ C_1$ $H_2 \ C_2$ $\vdots$ $H_N \ C_N$

输出格式

输出一行到标准输出，包含建设滑雪场的最小成本。

数据范围

• $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. (5 分) $K \ge 100\,000$，$H_i \le 300$，$C_i \le 100$ ($1 \le i \le N$)。
2. (12 分) $H_1 \le H_i$，$C_1 \le C_i$，$H_i \le 300$ ($1 \le i \le N$)。
3. (9 分) $N \le 10$，$H_i \le 10$ ($1 \le i \le N$)。
4. (33 分) $N \le 40$，$H_i \le 40$ ($1 \le i \le N$)。
5. (27 分) $H_i \le 300$ ($1 \le i \le N$)。
6. (14 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

8

说明 1

例如，滑雪场可以按以下方式建造：

1. 在点 1 执行两次路基工程，在点 5 执行一次。这些路基工程的总成本为 $2 \times (2 + 1) = 6$。结果，从点 1 开始各点的海拔变为 $2, 1, 0, 2, 2$ 米。
2. 在点 3 建造 KOI 酒店。
3. 在点 2 执行两次扩建工程。这些扩建工程的总成本为 $1 \times 2 = 2$。结果，从点 1 开始各点的连接设施数量变为 $1, 3, 1, 1, 1$。
4. 建造 4 条滑雪道：一条从点 1 到点 2，一条从点 2 到点 3，一条从点 4 到点 2，以及一条从点 5 到点 2。

此时，建设滑雪场的成本为 $6 + 2 = 8$。由于无法以 $7$ 或更低的成本建造滑雪场，因此输出 $8$。

该样例输入满足子任务 3, 4, 5, 6 的限制。

样例输入 2

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

样例输出 2

100010

说明 2

该样例输入仅在 $K$ 的值上与样例 1 不同。 该样例输入满足子任务 1, 3, 4, 5, 6 的限制。

样例输入 3

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

样例输出 3

108

说明 3

该样例输入满足子任务 2, 3, 4, 5, 6 的限制。