题目描述

在一条数轴上有编号从$1$到$N$的$N$栋房屋。第$i$栋房屋位于坐标$X_i$。多栋房屋可以位于同一坐标。

你需要在数轴上的任意实数坐标位置放置$M$个基站。然后，为每个基站设置一个非负整数的信号强度。

当一个基站的信号强度设置为 $x$ 时，该基站的信号可以覆盖到一栋房屋，当且仅当基站与房屋之间的距离不超过$x /2$。特别地，当$x=0$时，信号只能覆盖到与基站位于同一坐标的房屋。

你的任务是设置基站的位置和信号强度，使得每一栋房屋至少被一个基站的信号覆盖，并且所有基站的信号强度之和尽可能小。可以证明，在给定的约束条件下，答案总是一个整数。

约束条件

• $1 ≤ M ≤ N ≤ 5 × 10^5$
• $1 ≤ X_i ≤ 10^{12} (1 ≤ i ≤ N)$
• 所有输入值均为整数。

输入格式

输入从标准输入按以下格式给出：

$N \space M$

$X_1 \space X_2 \space... \space X_N$

输出格式

输出一个整数，表示满足条件的最小信号强度之和。

示例

输入示例1：

7 3
5 10 15 20 8 14 15

输出示例1：

6

解释

通过如下方式放置三个基站，信号可以覆盖所有房屋：

在坐标 7.5 处放置一个信号强度为 5 的基站。该基站可以覆盖房屋 1、2、5。

在坐标 14.5 处放置一个信号强度为 1 的基站。该基站可以覆盖房屋 3、6、7。

在坐标 20 处放置一个信号强度为 0 的基站。该基站仅覆盖房屋 4。

此时，信号强度的总和为 6。

由于无法找到一种信号强度总和小于 6 的布置方式，因此输出 6。

输入示例2：

7 7
5 10 15 20 8 14 15

输出示例2：

0

输入示例3：

7 1
5 10 15 20 8 14 15

输出示例3：

15

注意事项

Time Limit: 2 sec / Memory Limit: 1024 MiB