#1353. 养蜂人

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

题目描述

又到了养蜂人采集蜂蜜的时候。

养蜂人的 个蜂巢分布在了一条直线上,他每天只能采集一个蜂巢的蜂蜜,来来回回让他感觉十分麻烦。所以他决定从中选择 个蜂巢建立仓库,每天可以选择从其中一个仓库出发去采蜂蜜。

请问他应该如何建立这 个仓库,使得他采集完 个蜂巢需要走的距离之和最短?输出这个最短距离。

输入格式

第一行两个正整数 ,分别代表蜂巢的个数与仓库的个数。

接下来一行 个正整数 ,其中第 个代表从左到右第 个蜂巢与第 个蜂巢之间的距离。

输出格式

一行一个正整数,代表最短距离之和。

样例

样例输入

6 2
2 2 2 1 2

样例输出

7

样例解释

选择在第 个蜂巢建立仓库,这样可以选择从 号蜂巢处的仓库去采 号,从 号蜂巢处的仓库去采 号,距离之和为

数据范围与提示