문제

충남대학교 알고리즘 동아리방에는 $n$개의 좌석이 원형으로 배치되어 있으며, 시계방향으로 $1$부터 $n$까지 번호가 매겨져 있다 ($3 \le n \le 100$). 각 좌석은 시계방향으로 인접한 좌석과 연결되어 있으며, 모든 좌석은 외부와 연결된 개별 문을 하나씩 가지고 있다.

호정이는 각 좌석 $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 100$; $1 \le k \le 7$)

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

출력

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

예제 입력 1

6 2
2
5
4
2
6
2

예제 출력 1

14