405741: GYM102058 D Fascination Street

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

Unlike its name, the street is infamous to be a dark and eerie place in the night. To solve this, Robert decided to install the streetlight for some of the blocks. The cost of installing a streetlight for $$$i$$$-th block is $$$W_i$$$, and the total cost is the sum of each installation cost. After installing, every block should either have a streetlight, or have a streetlight in it's left or right block.

Robert also has some tricks to reduce the cost. Before installing the streetlight, Robert selects two distinct blocks $$$i$$$ and $$$j$$$, and exchange their position. After the operation, the cost of installation is exchanged. In other words, the operation simply swaps the value of $$$W_i$$$ and $$$W_j$$$. This operation have no cost, but Robert can only perform it at most $$$K$$$ times.

Now, given the array $$$W$$$ and the maximum possible number of operations $$$K$$$, you should find the minimum cost of lighting the whole street.

The first line contains two space-separated integers $$$N, K$$$. $$$N$$$ is the number of blocks, and $$$K$$$ is the maximum possible number of operations. ($$$1 \leq N \leq 250000 , 0 \leq K \leq 9$$$)

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

Print a single integer which contains the minimum cost of lighting the whole street.

5 0
1 3 10 3 1

4

5 1
1 3 10 3 1

2

12 0
317 448 258 208 284 248 315 367 562 500 426 390

1525

12 2
317 448 258 208 284 248 315 367 562 500 426 390

1107