#4409. [Usaco2016 Feb]Circular barn

题目描述

有一个N个点的环，相邻两个点距离是1。点顺时针标号为1..N。

最初每一个点是空的。

要求最终点i存在ri头牛。

你有∑ri头牛。你可以选择最多k个点，然后把你的牛任意分配在这k个点里。

之后，每一头牛可以选择不动，也可以顺时针走d格并呆在那里。这样，它要耗费d的能量。

（最初的分配不消耗能量）。

通过合理选择点、合理分配牛、合理安排牛的走动，使得消耗的总能量最小。

输入格式

第一行两个数N,k。

接下来N行每行一个数表示ri。

3<=N<=1000,

1<=k<=7,

1<=ri<=1000000

输出格式

输出一个数表示消耗的最小总能量。

样例

样例输入

6 2  

2  

5  

4  

2  

6  

2

样例输出

14

数据范围与提示