题目描述

桌上有 $N$ 个糖果横向排成一列，从左至右依次编号为 $1$ 至 $N$。第 $i$ 个糖果（$1 \le i \le N$）的美味度为 $A_i$。

JOI 君决定从这 $N$ 个糖果中选出若干个食用。

但为了避免吃糖过量，他规定：对于任意连续的 $K$ 个糖果，其中最多只能食用两个。换句话说，对于任意 $j$（$1 \le j \le N - K + 1$），在从第 $j$ 个到第 $j + K - 1$ 个的连续 $K$ 个糖果中，食用的糖果数量不能超过两个。

在此限制下，JOI 君希望使所选糖果的美味度总和尽可能大。

当给出 $N$ 个糖果的美味度及参数 $K$ 时，请编写程序，求出 JOI 君能获得的最大美味度总和。

输入格式

输入通过标准输入以如下格式给出：

$N$ $K$

$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

在标准输出中，以单行输出 JOI 君能获得的糖果美味度总和的最大值。

5 4
1 3 2 4 3

8

6 3
3 7 1 5 6 4

21

5 2
3 3 2 2 1

11

12 5
864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728

4427122428

提示

数据范围

• $2 \le K \le N \le 3\,000$。
• $1 \le A_i \le 10^9$（$1 \le i \le N$）。
• 所有输入值均为整数。

子任务

1. （4 分）$N \le 20$。
2. （19 分）$K \le 10$。
3. （47 分）$N \le 300$。
4. （30 分）无额外约束。

翻译由 Qwen3-235B 完成