[IOI2000] 邮局 加强版 加强版

> 看到你时总是感觉清风徐徐, > > 本以为和你相识不会是偶遇, > > 奈何你犹如过客、化作秋雨, > > 只是经过我生命的一瓢柳絮, > > 从不会真正有童话似的结局. > > 我静静地写尽这些躁言丑句, > > 本以为可以稍稍地缓解抑郁. > > 却是徒增一场悲伤的脑补剧. > > 你问我为什么说这么多? > > 因为这题是加强版的 [IOI2000]邮局.

高速公路旁边有 $n$ 个村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。两个位置之间的距离是其整数坐标差的绝对值。 现在要建立 $m$ 个邮局，邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。 你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

第一行包含两个整数，分别表示村庄的数量 $n$ 和邮局的数量 $m$。 第二行共 $n$ 个整数，表示每个村庄的坐标，第 $i$ 个整数表示第 $i$ 个村庄的坐标 $a_i$。

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

5 2
0 1 2 3 4

3

#### 数据规模与约定 本题共五个测试点，各测试点信息如下： | 测试点编号 | $n = $ | $a_i \leq $ | | :----------: | :-------: | :----: | | 1 | $50000$ | $6 \times 10^4$ | | 2 | $150000$ | $2 \times 10^5$ | | 3 | $299998$ | $5 \times 10^5$ | | 4 | $499998$ | $10^6$ | | 5 | $499999$ | $2\times 10^6$ | 对于全部的测试点，保证 $1 \leq m \leq n \leq 5 \times 10^5$，$0 \leq a_i \leq 2\times 10^6$，且 $a_i$ 的值在对应范围内均匀随机。 保证最终答案不超过 $10^9$。