题目描述

作为当代建筑的爱好者，Farmer John 建造了一个圆形新谷仓，谷仓内部 $n$ 个房间排成环形（$3 \leq n \leq 1000$），按顺时针顺序编号为 $1\ldots n$，每个房间都有通往与其相邻的左右房间的门，还有一扇门通往外面。

FJ 准备让第 $i$ 个房间里恰好有 $r_i$ 头奶牛（$1 \le r_i \le {10}^6$）。为了有序地让奶牛进入谷仓，他打算解锁 $k$ 个从外界进入谷仓的门（$1 \le k \le 7$）。然后，每头奶牛顺时针走动，直到到达目的地。FJ 的目标是让所有奶牛走动的距离和最小（奶牛从哪个门进入可以随意安排，这里走动的距离只包含进入谷仓后走动的距离），现在请你求出这个最小距离。

输入格式

第一行两个整数 $n,k$。

接下来 $n$ 行，第 $i$ 行一个整数 $r_i$。

输出格式

输出所有奶牛最小走动距离和。

6 2
2
5
4
2
6
2

14

提示

FJ 打开 $2,5$ 两个门。$11$ 头奶牛从 $2$ 号门进入，前往 $2,3,4$ 号房间，总距离 $8$。$10$ 头奶牛从 $5$ 号门进入，前往 $5,6,1$ 号房间，总距离 $6$。