该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

星尘收集

题目背景

在完成了对星环的探测后，噜噜和一只羊进入了一片名为 “JJJ” 的奇特星云。这片星云中漂浮着 $N$ 团明亮的星尘，它们排成了一条直线，从 $1$ 到 $N$ 编号。每一团星尘都蕴含着不同的能量。

他们的飞船上装备了一台“星尘收集器”，但这台设备有些特殊。为了防止能量过载，当收集器采集了第 $i$ 团星尘后，设备会进入短暂的冷却状态，此时无法立刻采集紧邻的第 $i+1$ 团星尘。

不过，一只羊为飞船准备了 $M$ 瓶“急冻剂”。每次使用一瓶急冻剂，都可以让收集器瞬间冷却，从而跳过冷却状态，允许飞船在采集了第 $i$ 团星尘后，继续采集第 $i+1$ 团。

现在，噜噜和一只羊想知道，在最多使用 $M$ 瓶急冻剂的情况下，他们最多能收集到多少总能量。

问题描述

给定一个长度为 $N$ 的正整数序列 $a_1, a_2, \ldots, a_N$，代表每团星尘的能量值。 你需要从中选择一个子序列，使得总能量和最大。 选择时需要遵循以下规则：

1. 如果你选择了 $a_i$ ($i < N$)，那么你不能选择 $a_{i+1}$。
2. 规则1有一个例外：你可以“使用一次急冻剂”来选择 $a_{i+1}$。这样的操作总共不能超过 $M$ 次。

请计算出可以获得的最大总能量。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示星尘的总数和急冻剂的数量。 第二行包含 $N$ 个用空格分隔的正整数 $a_1, a_2, \ldots, a_N$，表示每团星尘的能量值。

输出格式

输出一个整数，表示可以获得的最大总能量。

样例输入与输出

5 1
10 4 3 9 5

24

样例解释

星尘能量为 {10, 4, 3, 9, 5}，最多可以使用 1 瓶急冻剂。 最优策略：

• 采集第 1 团（10）。
• 跳过第 2 团。
• 采集第 4 团（9）。
• 使用 1 瓶急冻剂，继续采集第 5 团（5）。 总能量为 10 + 9 + 5 = 24。

数据规模与约定

• 对于 $100\%$ 的数据，$1 \le N \le 5000$, $0 \le M \le 5000$, $1 \le a_i \le 10^9$。

子任务划分:

• 子任务 1 (20分): $1 \le N \le 20$, $0 \le M \le N$。
• 子任务 2 (20分): $M = 0$, $1 \le N \le 2 \cdot 10^5$。
• 子任务 3 (20分): $1 \le N \le 500$, $0 \le M \le 500$。
• 子任务 4 (40分): 无特殊限制。