題目描述

桌子上橫著排成一列放有 $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

本範例輸入滿足所有子任務的限制。