← 返回题目列表

AtCoder · abc218_h

H. 红色和蓝色灯

中文机器翻译题面 查看原题

分数: 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