时间限制：1秒　　内存限制：256M

---

【题目描述】

　　X国的军营是一个圆形的建筑，内部的 \(N\) 个房间排成环形，按顺时针顺序编号为 \(1..N\)，每个房间都有通往与其相邻的左右房间的通道。其中第 \(i\) 个房间可以供 \(r_i\) 个士兵休息，军营的士兵总数刚好为 \(∑r_i\)。

　　现在需要打开 \(K\) 扇向外的门，外边的士兵可以随意选择这些门中的一个进入到建筑内。进入建筑内的士兵可以沿顺时针移动，每穿过一个房间之间的通道，耗费体力为 1。

　　现在需要你来确定，这 \(K\) 扇门开在哪些房间上，才能让所有士兵找到自己的房间耗费的体力和最小。

　　注意，不计算士兵在建筑外的移动而耗费的体力。

【输入格式】

　　第一行两个整数 \(N,K\)，接下来 \(N\) 行，第 \(i\) 行一个整数 \(r_i\)。

【输出格式】

　　输出所有士兵耗费体力的最小值。

【输入输出样例】

　Input

6 2
2
5
4
2
6
2 

　Output

14

【样例说明】

　　如下图，分别在 2, 5 号房间打开朝外的门：安排 11 名士兵从 2 号房间的门进入，有 5 名士兵直接住 2 号房间，有 4 名士兵前往 3 号房间，2 名士兵前往 4 号房间，则耗费体力为 8；安排 10 名士兵从 5 号房间的门进入，有 6 名士兵直接住 5 号房间，有 2 名士兵前往 6 号房间，2 名士兵前往 1 号房间，则耗费体力为 6。所以总体里为 6 + 8 = 14。

【数据限制】

　　\(100\%\) 的数据满足：\(1 ≤ N ≤ 100\)，\(1≤K≤7\)，\(1≤r_i≤1,000,000\)。

【来源】

　　Mr.he