8409: BZOJ4409:[Usaco2016 Feb]Circular barn

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

有一个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

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: