[IOI2000] 邮局 加强版 加强版

题目背景

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

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

5 2
0 1 2 3 4

输出样例 #1

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$。