题目描述

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

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

输入格式

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

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

输出格式

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

样例

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

9

数据范围

$1≤N≤300, 1≤P≤30$

来源

• IOI2000
• POJ1160
• 算法竞赛进阶指南