405757: GYM102059 G Fascination Street
Description
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.
InputThe 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$$$)
OutputPrint a single integer which contains the minimum cost of lighting the whole street.
ExamplesInput5 0Output
1 3 10 3 1
4Input
5 1Output
1 3 10 3 1
2Input
12 0Output
317 448 258 208 284 248 315 367 562 500 426 390
1525Input
12 2Output
317 448 258 208 284 248 315 367 562 500 426 390
1107