4412. 邮局

【题目描述】

Kyouko 曾经有一个梦想：邮递员。

高速公路旁边有 $n$ 个村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标表示。两个位置之间的距离是其整数坐标差的绝对值。

现在要建立 $m$ 个邮局，邮局将建在一些，但不一定是所有的村庄中。Kyouko  为了送邮件的时候轻松一些，打算选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

天才般的 Kyouko 秒杀了这个问题，所以这个问题给了你，你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

【输入格式】

第一行包含两个整数，分别表示村庄的数量 $n$ 和邮局的数量 $m$。

第二行共 $n$ 个整数，表示每个村庄的坐标，第 $i$ 个整数表示第 $i$ 个村庄的坐标 $a_i$。

【输出格式】

输出一行一个整数表示答案。

【样例输入】

5 2
0 1 2 3 4

【样例输出】

3

【数据规模与约定】

保证对于所有测试点 $1$：$n\le 50,0\le a_i\le 10^4$。

保证对于所有测试点 $2$：$n\le 500,0\le a_i\le 10^4$。

保证对于所有测试点 $3$：$n\le 2000,0\le a_i\le 10^4$。

保证对于所有测试点 $4$：$n\le 10^5,0\le a_i\le 2\times 10^6$。

保证对于所有测试点 $5$：$n\le 5\times 10^5,0\le a_i\le 2\times 10^6$。

【来源】

IOI2020 邮局加强版。