Fascination Street

Fascination Street이라는 거리는 길이가 같은 $N$개의 블록으로 나뉘어 있다. 각 블록 $i$ ($1 \leq i \leq N$)에 대해, $i > 1$이면 왼쪽에 블록 $i-1$이 있고, $i < N$이면 오른쪽에 블록 $i+1$이 있다.

이름과 달리 이 거리는 밤이 되면 어둡고 으스스하다. 이를 해결하려고 Robert는 일부 블록에 가로등을 설치하기로 했다. 블록 $i$에 가로등을 설치하는 비용은 $W_i$이고, 총비용은 각 설치 비용의 합이다. 설치한 뒤에는 모든 블록에 가로등이 있거나, 왼쪽 또는 오른쪽 블록에 가로등이 있어야 한다.

Robert는 교환으로 비용을 줄일 수 있다. 설치하기 전에 서로 다른 두 블록 $i$와 $j$를 골라 위치를 맞바꾸면, $W_i$와 $W_j$의 값이 서로 바뀐다. 교환 자체에는 비용이 들지 않지만, Robert가 수행할 수 있는 교환은 최대 $K$번이다.

배열 $W$와 교환 횟수의 상한 $K$가 주어졌을 때, 거리 전체를 밝히는 데 드는 최소 비용을 구하라.

첫 줄에 공백으로 구분된 두 정수 $N$과 $K$가 주어진다. $N$은 블록의 개수이고, $K$는 Robert가 수행할 수 있는 교환의 최대 횟수이다. ($1 \leq N \leq 250000$, $0 \leq K \leq 9$)

둘째 줄에는 공백으로 구분된 정수 $N$개 $W_1, W_2, \cdots, W_N$이 주어진다. $W_i$는 블록 $i$에 가로등을 설치하는 비용이다. ($0 \leq W_i \leq 10^9$)

거리 전체를 밝히는 최소 비용을 정수 하나로 출력한다.