A street named is divided into equal length of blocks. For each block (), it has block in its left side if , and block in its right side if .
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 -th block is , 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 and , and exchange their position. After the operation, the cost of installation is exchanged. In other words, the operation simply swaps the value of and . This operation have no cost, but Robert can only perform it at most times.
Now, given the array and the maximum possible number of operations , you should find the minimum cost of lighting the whole street.
输入格式
The first line contains two space-separated integers . is the number of blocks, and is the maximum possible number of operations. ()
The second line contains space-separated integers , where is the cost of installing a streetlight for -th block. ()
输出格式
Print a single integer which contains the minimum cost of lighting the whole street.
