题目描述

在涉及农夫约翰的圆形谷仓的最后一次崩溃之后，人们会认为他已经吸取了有关非传统建筑的教训。

然而，他认为他仍然可以通过允许多头奶牛进入每个房间来使他的圆形牛舍（来自前面的问题）正常运行。

回顾一下，谷仓由一圈$\red{n }$个房间组成，从谷仓周边的 $\red{1…}$$\red{n}$顺时针编号 $\red{(3≤}$$\red{n≤}$$\red{100)}$。每个房间都有通往两个相邻房间的门，还有一扇通往谷仓外部的门。

$\red{Farmer John }$希望 $\red{ri}$奶牛最终进入房间$\red{i (1≤}$$\red{ri≤}$$\red{1,000,000)}$。为了让奶牛有条不紊地进入牛舍，他计划打开$\red{k }$个外门（$\red{1≤}$$\red{k≤}$$\red{7）}$，只允许奶牛通过这些门进入。然后每头奶牛顺时针穿过房间，直到到达合适的目的地。

$\red{Farmer John }$想要解锁外门，这将导致他的奶牛在进入牛舍后集体行走最少的总距离（他们最初可以在$\red{k}$未上锁的门 外排队，但是他们喜欢；这不会影响总距离问题）。

如果他选择最好的$\red{k }$门来解锁，请确定他的奶牛需要步行的最小总距离。

输入格式

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

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

输出格式

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

样例

输入样例

6 2
2
5
4
2
6
2

输出样例

14

提示

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

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