[IOI2000]邮局

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file postoffice.in Output file postoffice.out

【题目描述】

有一条笔直的高速公路,路旁分布着一些村庄。公路可以用一条数轴表示,则村庄的位置就是其坐标。没有两个村庄的坐标相同。两个村庄之间的距离就是它们坐标之差的绝对值。

一些——但不一定是所有的村庄将修建邮局。邮局和该邮局所在的村庄处于同一位置。应当仔细选择邮局的位置,使得所有村庄到最近邮局的距离总和最短。

你要编写一个程序,给出所有村庄的坐标和计划修建的邮局个数,计算所有村庄到最近邮局的距离总和的最小可能值。

【输入格式】

输入文件的第一行有2个正整数:村庄数V(1<=V<=300),邮局数P(1<=P<=30),P<=V。

第二行有V个正整数,分别代表N个村庄的坐标。坐标的范围是[1,10000],坐标按递增顺序给出。

【输出格式】

输出一行一个正整数S,即所有村庄到最近邮局的距离总和的最小可能值。

【样例输入】

10 5

1 2 3 6 7 9 11 22 44 50

【样例输出】

9

【提示】

对于30%的数据,1<=P<=N<=10.

对于100%的数据,1<=P<=30,1<=N<=300,P<=N.