题目描述

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

翁老师决定从这 $n$ 个糖果中选出若干个食用。

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

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

当给出 $n$ 个糖果的美味度及参数 $k$ 时，请编写程序，求出 翁老师 能获得的最大美味度总和。

输入格式

第一行输入两个正整数 $n$ 和 $k$。

第二行输入 $n$ 个空格隔开的整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出 翁老师 能获得的糖果美味度总和的最大值。

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

提示

数据范围

对于 $100\%$ 的数据满足：

• $2 \le k \le n \le 3000$。
• $1 \le a_i \le 10^9$

本题采取捆绑测试

• 子任务 1（$20$ 分）：$n\leq 20$。
• 子任务 2（$20$ 分）：$k\leq 10$。
• 子任务 3（$20$ 分）：$n\leq 300$。
• 子任务 4（$40$ 分）：无特殊限制。