{"problem":{"name":"Red and Blue Lamps","description":{"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. For each $i=1,\\ldots,N-1$, a reward of $A_i$ is given if Lamp $i$ and Lamp ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc218_h"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $R$\n$A_1$ $A_2$ $\\ldots$ $A_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc218_h","tags":[],"sample_group":[["6 2\n3 1 4 1 5","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$."],["7 6\n2 7 1 8 2 8","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$."],["11 7\n12345 678 90123 45678901 234567 89012 3456 78901 23456 7890","46207983"]],"created_at":"2026-03-03 11:01:14"}}