题目描述

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

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

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

输入输出格式

输入格式

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

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

输出格式

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

输入输出样例

输入样例 #1

5 2
0 1 2 3 4

输出样例 #1

3

说明

数据规模与约定

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

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

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

luogu 6246，数据纯随机