题目描述

作为当代建筑的爱好者，农民约翰建造了一个完美圆形的新谷仓。

在内部，谷仓由${n}$个房间组成，围绕谷仓的周长从${1…}$${n}$顺时针编号${（3≤}$${n≤}$${1,000). }$

每个房间都有通向两个相邻房间的门，还有一扇通向谷仓外部的门。 农民约翰希望奶牛最终进入房间${i}$的奶牛有${(1≤r_i}$${≤}$${10^6) }$头

为了有序地将奶牛赶到牲口棚，他计划打开${k}$扇外门${（1}$${≤}$${k≤}$${7）}$ 只允许奶牛通过这些门 进入。

然后每头奶牛顺时针穿过房间，直到到达合适的目的地。农民约翰想要打开外部的门，使他的奶牛在进入谷仓后集体行走最少的总距离（他们最初可以在${k}$个未锁的门外按自己喜欢的方式排队；这不影响所讨论的总距离）。

如果他选择最好的${k}$门开锁，请确定他的奶牛需要走的最小总距离。

输入格式

第一行输入包含${n}$和${k}$。

剩余的每个${n}$行包含${r1…}$${rn}$

输出格式

请写出奶牛需要走的最小距离。

样例

输入样例

6 2
2
5
4
2
6
2

输出样例

14

提示

农夫约翰可以打开${2}$号门和${5}$号门。${11}$头牛从${2}$号门进入，总共走了${8}$步才能到达${2}$号 、${3}$号和${4}$号房间。

${10}$头牛从${5}$号门进入，总共走${6}$步，到达${5}$号、${6}$号和${1}$号房间。