P3140 [USACO16FEB] Circular Barn Revisited G

题目描述

在上一次涉及 Farmer John 的圆形谷仓的惨败之后，人们可能会认为他已经吸取了关于非传统建筑的教训。然而，他认为通过允许每间房间进入多头奶牛，仍然可以让他那个圆形谷仓（来自之前的问题）正常运作。回顾一下，谷仓由 $n$ 个房间组成，这些房间顺时针编号为 $1 \ldots n$，围绕谷仓的周边排列（$3 \leq n \leq 100$）。每个房间都有通往两个相邻房间的门，还有一扇门通向谷仓的外部。

Farmer John 希望最终有恰好 $r_i$ 头奶牛进入房间 $i$（$1 \leq r_i \leq 1,000,000$）。为了让奶牛有序地进入谷仓，他计划解锁 $k$ 扇外部门（$1 \leq k \leq 7$），只允许奶牛通过这些门进入。每头奶牛随后顺时针穿过房间，直到到达合适的目的地。Farmer John 希望解锁那些能让他的奶牛在进入谷仓后总共行走的距离最小的外部门（它们最初可以在 $k$ 扇解锁的门外任意排列；这不会计入总距离）。请确定如果他选择最佳的 $k$ 扇门解锁，他的奶牛需要行走的最小总距离。

输入格式

输入的第一行包含 $n$ 和 $k$。接下来的 $n$ 行每行包含 $r_1 \ldots r_n$。

输出格式

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

输入输出样例 1

6 2
2
5
4
2
6
2

14

说明/提示

Farmer John 可以解锁门 2 和门 5。11 头奶牛从门 2 进入，总共行走 8 的距离到达房间 2、3 和 4。10 头奶牛从门 5 进入，总共行走 6 的距离到达房间 5、6 和 1。