AT_abc414_d [ABC414D] Transmission Mission

在数轴上有 $N$ 栋房子，编号为 $1$ 到 $N$。第 $i$ 栋房子位于坐标 $X_i$。可能有多栋房子位于同一坐标。 你需要在数轴上的任意实数坐标处放置 $M$ 个基站，并为每个基站设置一个非负整数的**电波强度**。 对于某个基站，如果其电波强度为 $x$，则该基站能覆盖的房子为与其距离不超过 $\displaystyle\frac{x}{2}$ 的房子。特别地，当 $x=0$ 时，该基站只能覆盖与其在同一坐标的房子。 请你选择基站的位置和电波强度，使得每一栋房子都至少被一个基站覆盖，并且所有基站的电波强度之和最小。输出这个最小的电波强度总和。 可以证明，对于任意满足条件的输入，答案都是整数。

输入通过标准输入给出，格式如下： > $N$ $M$ > $X_1$ $X_2$ $\dots$ $X_N$

请输出一个整数，表示最小的电波强度总和。

## 限制条件 - $1 \leq M \leq N \leq 5 \times 10^5$ - $1 \leq X_i \leq 10^{12}$（$1 \leq i \leq N$） - 输入的所有数值均为整数。 ## 样例解释 1 如下图所示，放置 $3$ 个基站可以覆盖所有房子： - 在坐标 $7.5$ 处放置一个电波强度为 $5$ 的基站，该基站可以覆盖房子 $1,2,5$。 - 在坐标 $14.5$ 处放置一个电波强度为 $1$ 的基站，该基站可以覆盖房子 $3,6,7$。 - 在坐标 $20$ 处放置一个电波强度为 $0$ 的基站，该基站可以覆盖房子 $4$。 此时电波强度总和为 $6$。无法通过更小的电波强度总和覆盖所有房子，因此输出 $6$。 由 ChatGPT 4.1 翻译