Fascination Street

A street named Fascination Street is divided into $N$ blocks of equal length. For each block $i$ ($1 \leq i \leq N$), block $i-1$ is on its left if $i > 1$, and block $i+1$ is on its right if $i < N$.

Despite its name, the street is dark and eerie at night. To fix this, Robert decided to install streetlights on some of the blocks. Installing a streetlight on block $i$ costs $W_i$, and the total cost is the sum of the installation costs. After installation, every block must either have a streetlight, or have a streetlight on its left or right neighbor.

Robert can reduce the cost with swaps. Before installing, he picks two distinct blocks $i$ and $j$ and swaps their positions, which swaps the values of $W_i$ and $W_j$. A swap costs nothing, but Robert can perform at most $K$ swaps.

Given the array $W$ and the maximum number of swaps $K$, find the minimum cost to light the whole street.

The first line contains two integers $N$ and $K$, separated by a space. $N$ is the number of blocks, and $K$ is the maximum number of swaps Robert can perform. ($1 \leq N \leq 250000$, $0 \leq K \leq 9$)

The second line contains $N$ integers $W_1, W_2, \cdots, W_N$, separated by spaces, where $W_i$ is the cost of installing a streetlight on block $i$. ($0 \leq W_i \leq 10^9$)

Print a single integer: the minimum cost to light the whole street.