UOJ Logo Universal Online Judge

UOJ

#873. 【JOISC2024】滑雪 2

附件下载 统计

JOI 先生管理着 IOI 高原上一家著名的滑雪度假村,他决定为滑雪度假村开业 15 周年庆祝活动而在相邻的 KOI 高原上建造一家新的滑雪度假村。

KOI 高原有 N 个点,编号从 1N。目前,第 i 个点(1iN)的海拔高度为 Hi 米,并且高原上的每个点都没有连接起来的滑道。此外,每个点都配备了一个未使用的连接设施。

JOI 先生的目标是在高原上的一个点上建造 KOI 酒店,然后建造一些滑道连接高原上的每个点,以便人们可以从任何一个点滑雪到酒店。具体来说,JOI 先生将按照以下步骤建造滑雪度假村:

  1. 进行以下筑堤工作任意次数(可能为零):选择一个点 i,将点 i 的海拔高度增加 1 米。此工作的成本为每次操作 K

  2. N 个点中选择一个点,并在那里建造 KOI 酒店。

  3. 进行以下扩展工作任意次数(可能为零):选择一个点 i,在点 i 建造一个连接设施。此工作的成本为每次操作 Ci

  4. 对于除了 KOI 酒店所在点之外的剩余 N1 个点,执行以下构建:设 i 为该点的编号。选择另一个海拔严格较低的点 j,并使用点 j 的一个未使用的连接设施,从点 i 向点 j 构建单向滑道。注意,如果没有海拔严格较低且有未使用连接设施的点 j,则无法实现目标。

滑雪度假村的建造成本是进行堤岸工作和扩展工作的成本之和。

编写一个程序,给定 KOI 高原上每个点的信息和每次筑堤工作的成本 K,找到建造滑雪度假村的最小成本。

输入格式

从标准输入中读取以下数据:

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

输出格式

输出一行,构建滑雪度假村的最小成本。

样例输入 1

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

样例输出 1

8

样例解释 1

例如,可以按以下方式建造滑雪度假村:

  1. 在点 1 进行两次筑堤工作,在点 5 进行一次。这些筑堤工作的总成本为 2×(2+1)=6。每个点的海拔高度变为 2,1,0,2,2 米。
  2. 在点 3 建造 KOI 酒店。
  3. 在点 2 进行两次扩展工作。这些扩展工作的总成本为 1×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

这个样例输入与示例输入 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

样例输出 3

108

样例解释 3

此示例输入满足子任务 2,3,4,5,6 的约束条件。

约束条件

  • 1N300
  • 1K109
  • 0Hi1091iN
  • 1Ci1091iN
  • 给定的值均为整数。

子任务

  1. (5 分) K100,000Hi300Ci1001iN
  2. (12 分) H1HiC1CiHi3001iN
  3. (9 分) N10Hi101iN
  4. (33 分) N40Hi401iN
  5. (27 分) Hi3001iN
  6. (14 分) 无额外约束。