P14535 [OII 2025] 木材运输 / Trasporto tronchi

译自 [Italian Olympiad in Informatics (OII) 2025 - Trasporto tronchi](https://training.olinfo.it/task/oii_alberi)。 OII 2025 纪念碑的建造准备工作已经开始。为了清理场地，一些树木被砍伐，现在需要将它们装上卡车运往木工车间。

初始时，第 $i$ 棵树位于位置 $A_i$，卡车位于位置 $0$。 在开始装载之前，可以对一些树木进行修剪：修剪一棵树的成本为 $K$，可以使树干变得光滑，从而可以在其他光滑的树干上滚动。 树木可以通过两种方式移动： - 任何树都可以向卡车方向移动一个位置（该位置必须是空的），代价为 $1$。 - 如果一棵**被修剪的**树的紧左侧有一个或多个连续的**被修剪的**树，并且这些树左侧紧接着一个空位，那么这棵树可以在这些树上滚动（但不能在未修剪的树或地面上滚动）直到到达空位，代价为 $1$。 卡车所在的位置被视为一个空位置。 请帮助组织者确定将所有树木装上卡车的最小代价。 ### 实现细节 附件中包含一个实现示例 `alberi.cpp`。 你需要实现如下函数： ``` long long carica(int N, int K, vector A); ``` - $N$：树木的数量。 - $K$：修剪一棵树的成本。 - $A$：下标从 $0$ 到 $N-1$，包含树木的初始位置。 - 该函数需要返回将所有树木带到位置 $0$ 的最小代价。 - 对于每个测试点，该函数都只会被调用一次。

评测程序的输入格式如下： - 第 $1$ 行：$N\ K$ - 第 $2$ 行：$A_0\ A_1\ \ldots\ A_{N-1}$

评测程序的输出格式如下： 输出一行一个整数，表示函数 `carica` 的返回值。

#### 【样例解释】 在样例 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$ | $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$ | 无额外限制 |