题目描述

有 $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}$

输出

打印答案。

示例输入1

6 2
3 1 4 1 5

示例输出1

11

将第 $3, 5$ 盏灯点亮为红色，将第 $1, 2, 4, 6$ 盏灯点亮为蓝色，能够得到的总奖励为 $A_2+A_3+A_4+A_5=11$。

由于无法得到更多奖励，所以答案是 $11$。

示例输入2

7 6
2 7 1 8 2 8

示例输出2

10

将第 $1, 2, 3, 4, 5, 7$ 盏灯点亮为红色，将第 $6$ 盏灯点亮为蓝色，能够得到的总奖励为 $A_5+A_6=10$。

示例输入3

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

示例输出3

46207983