红色与蓝色灯泡

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的灯泡排成一行。你要把其中 $R$ 个点亮成红色，其余 $N-R$ 个点亮成蓝色。

对每个 $i=1,\ldots,N-1$，如果灯泡 $i$ 和灯泡 $i+1$ 亮起不同颜色，则获得 $A_i$ 的奖励。

请找出通过合理决定灯泡颜色所能获得的最大总奖励。

输入格式

输入按以下格式从标准输入给出。

$N$ $R$
$A_1$ $A_2$ $\ldots$ $A_{N-1}$

输出格式

输出答案。

样例

6 2
3 1 4 1 5

11

把灯泡 $3, 5$ 点亮成红色，灯泡 $1, 2, 4, 6$ 点亮成蓝色，总奖励为 $A_2+A_3+A_4+A_5=11$。

不可能获得更多奖励，所以答案为 $11$。

7 6
2 7 1 8 2 8

10

把灯泡 $1, 2, 3, 4, 5, 7$ 点亮成红色，灯泡 $6$ 点亮成蓝色，总奖励为 $A_5+A_6=10$。

11 7
12345 678 90123 45678901 234567 89012 3456 78901 23456 7890

46207983

数据范围

• $2 \leq N \leq 2\times 10^5$
• $1 \leq R \leq N-1$
• $1 \leq A_i \leq 10^9$
• 输入中的值全部为整数