一条笔直的高速公路上有N个村庄，每个村庄都有一个整数位置坐标，不同村庄的坐标不同，现在要在其中的 P 个村庄上建立邮局。

请问如何安排邮局的位置可以使得每个村庄到其最近邮局的距离和最小，输出这个最小值。

输入格式

第一行包含两个整数N和P，分别表示村庄数量以及邮局数量。

第二行包含N个整数，表示N个村庄的位置坐标，坐标均为不超过10000的正整数。

输出格式

输出一个整数，表示距离和的最小值。

数据范围

$1 \le N \le 300$,
$1 \le P \le 30$,

输入样例：

10 5
1 2 3 6 7 9 11 22 44 50

输出样例：

9

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解