H - 红色和蓝色的灯

分数：$600$ 点

问题描述

有 $N$ 盏灯，编号从 $1$ 到 $N$，排列成一行。你将会用红色点亮其中的 $R$ 盏灯，蓝色点亮其中的 $N-R$ 盏灯。

对于每一个 $i=1,\ldots,N-1$，如果第 $i$ 盏灯和第 $i+1$ 盏灯点亮的颜色不同，你将会得到奖励 $A_i$。

求出通过有效地决定灯的颜色所能得到的最大总奖励。

约束

• $2 \leq N \leq 2\times 10^5$
• $1 \leq R \leq N-1$
• $1 \leq A_i \leq 10^9$
• 所有输入的值均为整数。

输入

输入数据从标准输入给出，具体格式如下：

$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

用红色点亮灯 $1, 2, 3, 4, 5, 6, 8$，用蓝色点亮灯 $7, 9, 10, 11$，总奖励为 $A_2+A_3+A_4+A_5+A_6+A_8+A_9+A_{10}+A_{11}=46207983$。