题目描述

桌子上横着排成一列放有 $N$ 颗糖果，从左到右依次编号为从 $1$ 到 $N$。糖果 $i$（$1 \le i \le N$）的美味度为 $A_i$。

JOI 君决定从这 $N$ 颗糖果中选择若干颗吃掉。

不过，为了不吃太多糖果，对于任意连续的 $K$ 颗糖果，他最多只吃其中的 $2$ 颗。也就是说，对于任意 $j$（$1 \le j \le N - K + 1$），在从糖果 $j$ 到糖果 $j + K - 1$ 的连续 $K$ 颗糖果中，吃掉的糖果数量必须不超过 $2$ 颗。

在此前提下，JOI 君希望吃掉的糖果的美味度之和尽可能大。

给定 $N$ 颗糖果的美味度与 $K$，请编写程序，求出 JOI 君吃掉的糖果的美味度之和的最大值。

数据范围

• $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$ 分）无额外限制。

输入格式

输入从标准输入按以下格式给出：

N K
A_1 A_2 ... A_N

输出格式

向标准输出在 $1$ 行内输出 JOI 君吃掉的糖果的美味度之和的最大值。

样例

样例输入 1

5 4
1 3 2 4 3

样例输出 1

8

当 JOI 君吃掉糖果 $1$、糖果 $4$、糖果 $5$ 时，美味度之和为 $8$。

在对于任意连续 $4$ 颗糖果吃掉的糖果数量都不超过 $2$ 颗的吃法中，不存在美味度之和达到 $9$ 或以上的方案，因此输出 $8$。

该样例输入满足所有子任务的限制。

样例输入 2

6 3
3 7 1 5 6 4

样例输出 2

21

当 JOI 君吃掉糖果 $1$、糖果 $2$、糖果 $4$、糖果 $5$ 时，美味度之和为 $21$。

在对于任意连续 $3$ 颗糖果吃掉的糖果数量都不超过 $2$ 颗的吃法中，不存在美味度之和达到 $22$ 或以上的方案，因此输出 $21$。

该样例输入满足所有子任务的限制。

样例输入 3

5 2
3 3 2 2 1

样例输出 3

11

该样例输入满足所有子任务的限制。

样例输入 4

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

样例输出 4

4427122428

该样例输入满足所有子任务的限制。