题目背景

译自 Italian Olympiad in Informatics (OII) 2025 - Trasporto tronchi。

OII 2025 纪念碑的建造准备工作已经开始。为了清理场地，一些树木被砍伐，现在需要将它们装上卡车运往木工车间。

题目描述

初始时，第 $i$ 棵树位于位置 $A_i$，卡车位于位置 $0$。

在开始装载之前，可以对一些树木进行修剪：修剪一棵树的成本为 $K$，可以使树干变得光滑，从而可以在其他光滑的树干上滚动。

树木可以通过两种方式移动：

• 任何树都可以向卡车方向移动一个位置（该位置必须是空的），代价为 $1$。
• 如果一棵被修剪的树的紧左侧有一个或多个连续的被修剪的树，并且这些树左侧紧接着一个空位，那么这棵树可以在这些树上滚动（但不能在未修剪的树或地面上滚动）直到到达空位，代价为 $1$。

卡车所在的位置被视为一个空位置。

请帮助组织者确定将所有树木装上卡车的最小代价。

实现细节

附件中包含一个实现示例 alberi.cpp。

你需要实现如下函数：

long long carica(int N, int K, vector<int> A);

• $N$：树木的数量。
• $K$：修剪一棵树的成本。
• $A$：下标从 $0$ 到 $N-1$，包含树木的初始位置。
• 该函数需要返回将所有树木带到位置 $0$ 的最小代价。
• 对于每个测试点，该函数都只会被调用一次。

输入格式

评测程序的输入格式如下：

• 第 $1$ 行：$N\ K$
• 第 $2$ 行：$A_0\ A_1\ \ldots\ A_{N-1}$

输出格式

评测程序的输出格式如下：

输出一行一个整数，表示函数 carica 的返回值。

3 2
1 5 6

11

6 3
1 4 5 10 12 14

30

提示

【样例解释】

在样例 1 中，一种使代价最小的方案为：

• 对位置在 $5,6$ 的树进行修剪；
• 在修剪之后只需要 $7$ 次移动，总代价为 $7+2\cdot 2=11$。

在样例 2 中，一种使代价最小的方案是修剪除了第一棵树之外的所有树。

【数据范围】

• $1 \leq N \leq 5\times 10^5$；
• $0 \leq K \leq 10^9$；
• $1 \leq A_i \leq 10^9$；
• $A_i < A_{i+1}$。

【子任务】

子任务编号	分值	约束条件
$0$		样例
$1$	$11$	$K = 10^9$
$2$	$17$	$K = 0$，$N \leq 500$ 且 $1 \leq A_i \leq 2000$
$3$	$22$	$K = 0$
$4$	$23$	$K \leq 2000$，$N \leq 500$ 且 $1 \leq A_i \leq 2000$
$5$	$27$	无额外限制