问题陈述
您正在为即将到来的 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