{"raw_statement":[{"iden":"problem statement","content":"There are $N$ lamps numbered $1$ through $N$ arranged in a row. You are going to light $R$ of them in red and $N-R$ in blue.\nFor each $i=1,\\ldots,N-1$, a reward of $A_i$ is given if Lamp $i$ and Lamp $i+1$ light up in different colors.\nFind the maximum total reward that can be obtained by efficiently deciding the colors of the lamps."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq R \\leq N-1$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $R$\n$A_1$ $A_2$ $\\ldots$ $A_{N-1}$"},{"iden":"sample input 1","content":"6 2\n3 1 4 1 5"},{"iden":"sample output 1","content":"11\n\nLighting up Lamps $3, 5$ in red and Lamps $1, 2, 4, 6$ in blue yields a total reward of $A_2+A_3+A_4+A_5=11$.\nYou cannot get any more, so the answer is $11$."},{"iden":"sample input 2","content":"7 6\n2 7 1 8 2 8"},{"iden":"sample output 2","content":"10\n\nLighting up Lamps $1, 2, 3, 4, 5, 7$ in red and Lamp $6$ in blue yields a total reward of $A_5+A_6=10$."},{"iden":"sample input 3","content":"11 7\n12345 678 90123 45678901 234567 89012 3456 78901 23456 7890"},{"iden":"sample output 3","content":"46207983"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}