#3459. 邮局 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

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

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

输入格式

第一行包含两个整数N和P。

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

输出格式

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

样例

样例输入

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

样例输出

9

数据范围与提示

,

,