← 返回题目列表

AtCoder · past202309_h

H. 休憩

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

问题陈述

您正在为即将到来的 N天假期。

每天,你要么“玩”,要么“学习”。
其中 N 天,你至少需要学习 M 天。
您不会连续两天或以上学习。
如果您当天玩 i,你会得到一个 喜悦 of A_i;如果你学习,快乐就是 0 那天。

找出最大可能的总快乐 N 天。

约束

  • 1 \leq N \leq 3000
  • 0 \leq M \leq \frac{N+1}{2}
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 \ldots A_N

输出

打印答案。


样本输入 1

5 2
3 2 4 1 5

示例输出 1

12

您可以在几天内玩 1, 3,和 5,日间学习 2 和 4 获得快乐 12.


示例输入 2

5 2
3 5 4 1 2

示例输出 2

11

您可以在几天内玩 2, 3,和 5,日间学习 1 和 4 获得快乐 11.
请注意,您不能连续学习两天或以上。


示例输入 3

10 0
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

示例输出 3

10000000000