题目背景

看到你时总是感觉清风徐徐,

本以为和你相识不会是偶遇,

奈何你犹如过客、化作秋雨,

只是经过我生命的一瓢柳絮,

从不会真正有童话似的结局.

我静静地写尽这些躁言丑句,

本以为可以稍稍地缓解抑郁.

却是徒增一场悲伤的脑补剧.

你问我为什么说这么多?

因为这题是加强版的 [IOI2000]邮局.

题目描述

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

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

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

输入格式

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

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

输出格式

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

5 2
0 1 2 3 4

3

提示

数据规模与约定

本题共五个测试点，各测试点信息如下：

对于全部的测试点，保证 $1 \leq m \leq n \leq 5 \times 10^5$，$0 \leq a_i \leq 2\times 10^6$，且 $a_i$ 的值在对应范围内均匀随机。

保证最终答案不超过 $10^9$。