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 翻译