又到了养蜂人采集蜂蜜的时候。
养蜂人的 个蜂巢分布在了一条直线上,他每天只能采集一个蜂巢的蜂蜜,来来回回让他感觉十分麻烦。所以他决定从中选择 个蜂巢建立仓库,每天可以选择从其中一个仓库出发去采蜂蜜。
请问他应该如何建立这 个仓库,使得他采集完 个蜂巢需要走的距离之和最短?输出这个最短距离。
第一行两个正整数 ,分别代表蜂巢的个数与仓库的个数。
接下来一行 个正整数 ,其中第 个代表从左到右第 个蜂巢与第 个蜂巢之间的距离。
一行一个正整数,代表最短距离之和。
样例输入
6 2 2 2 2 1 2
样例输出
7
样例解释
选择在第 个蜂巢建立仓库,这样可以选择从 号蜂巢处的仓库去采 号,从 号蜂巢处的仓库去采 号,距离之和为 。