Opis zadania

Na biurku leży w jednym poziomym rzędzie $N$ cukierków, ponumerowanych od lewej do prawej liczbami od $1$ do $N$. Smakowitość cukierka $i$ ($1 \le i \le N$) wynosi $A_i$.

JOI-kun postanowił wybrać kilka spośród $N$ cukierków i je zjeść.

Jednak aby nie zjeść zbyt wielu cukierków, spośród dowolnych $K$ kolejnych cukierków zjada co najwyżej $2$. Innymi słowy, dla każdego $j$ ($1 \le j \le N - K + 1$), spośród $K$ kolejnych cukierków od cukierka $j$ do cukierka $j + K - 1$, liczba zjedzonych cukierków nie może przekraczać $2$.

Przy tym warunku JOI-kun chciałby, aby suma smakowitości zjedzonych przez niego cukierków była jak największa.

Mając dane smakowitości $N$ cukierków oraz liczbę $K$, napisz program, który wyznaczy maksymalną możliwą sumę smakowitości cukierków zjedzonych przez JOI-kuna.

Ograniczenia

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Wszystkie wartości wejściowe są liczbami całkowitymi.

Podzadania

1. ($4$ punkty) $N \le 20$.
2. ($19$ punktów) $K \le 10$.
3. ($47$ punktów) $N \le 300$.
4. ($30$ punktów) Brak dodatkowych ograniczeń.

Wejście

Wejście podawane jest ze standardowego wejścia w następującym formacie:

N K
A_1 A_2 ... A_N

Wyjście

Na standardowe wyjście wypisz w $1$ wierszu maksymalną możliwą sumę smakowitości cukierków zjedzonych przez JOI-kuna.

Przykłady

Przykład wejścia 1

5 4
1 3 2 4 3

Przykład wyjścia 1

8

Gdy JOI-kun zje cukierek $1$, cukierek $4$ oraz cukierek $5$, suma smakowitości wyniesie $8$.

Wśród sposobów zjedzenia cukierków, w których spośród dowolnych $4$ kolejnych cukierków zjadane są co najwyżej $2$, nie istnieje taki, dla którego suma smakowitości wynosiłaby $9$ lub więcej, dlatego wypisujemy $8$.

Ten przykład wejścia spełnia ograniczenia wszystkich podzadań.

Przykład wejścia 2

6 3
3 7 1 5 6 4

Przykład wyjścia 2

21

Gdy JOI-kun zje cukierek $1$, cukierek $2$, cukierek $4$ oraz cukierek $5$, suma smakowitości wyniesie $21$.

Wśród sposobów zjedzenia cukierków, w których spośród dowolnych $3$ kolejnych cukierków zjadane są co najwyżej $2$, nie istnieje taki, dla którego suma smakowitości wynosiłaby $22$ lub więcej, dlatego wypisujemy $21$.

Ten przykład wejścia spełnia ograniczenia wszystkich podzadań.

Przykład wejścia 3

5 2
3 3 2 2 1

Przykład wyjścia 3

11

Ten przykład wejścia spełnia ograniczenia wszystkich podzadań.

Przykład wejścia 4

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

Przykład wyjścia 4

4427122428

Ten przykład wejścia spełnia ograniczenia wszystkich podzadań.