分数: 600 点
问题陈述
有 N 灯编号 1 通过 N 排列成一排。你将要点亮 R 其中红色和 N-R 为蓝色。
对于每个 i=1,\ldots,N-1,奖励为 如果灯给出 A_i 给出如果灯 i 和灯 i+1 以不同的颜色亮起。
找出通过有效地决定灯的颜色可以获得的最大总奖励。
约束
- 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