題目描述

張檯上面橫排擺咗 $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

呢個樣例輸入滿足所有子任務嘅限制。