문제

기원이는 현대 건축에 관심이 많아, 완벽한 원형 모양의 새로운 건물을 지었다. 건물 내부에는 $n$개의 방이 원형으로 배열되어 있으며, 시계 방향으로 $1$번부터 $n$번까지 번호가 매겨져 있다 ($3 \le n \le 1,000$). 각 방은 인접한 두 개의 방으로 연결되는 내부 문이 있고, 건물 외부로 통하는 외부 문도 하나씩 있다.

기원이는 $i$번 방에 정확히 $r_i$명의 학생이 들어가기를 원한다 ($1 \le r_i \le 1,000,000$). 학생들을 질서 있게 입장시키기 위해, 기원이는 $k$개의 외부 문만 개방하여 학생들을 그 문을 통해서만 들어오게 할 계획이다 ($1 \le k \le 7$). 각 학생은 개방된 문 중 하나를 통해 건물로 들어온 뒤, 목적지에 도착할 때까지 시계 방향으로 방을 이동한다. 기원이는 학생들이 이동하는 총 거리의 합이 최소가 되도록 $k$개의 외부 문을 선택하려고 한다. 학생들은 건물 외부에서 어느 문 앞에 줄을 설지 자유롭게 정할 수 있으며, 건물 밖에서의 이동 거리는 합계에 포함되지 않는다. 기원이가 최적의 $k$개 문을 선택했을 때, 학생들이 이동해야 하는 총 거리의 최솟값을 구하시오.

입력

첫째 줄에 $n$과 $k$가 공백으로 구분되어 주어진다. ($3 \le n \le 1,000$; $1 \le k \le 7$)

이어서 $n$개의 줄에 $r_1, r_2, \dots, r_n$이 한 줄에 하나씩 주어진다. ($1 \le r_i \le 1,000,000$)

출력

학생들이 이동해야 하는 총 거리의 최솟값을 출력한다.

예제 입력 1

6 2
2
5
4
2
6
2

예제 출력 1

14