Aufgabenbeschreibung

Auf einem Tisch liegen $N$ Bonbons in einer horizontalen Reihe nebeneinander, die von links nach rechts von $1$ bis $N$ nummeriert sind. Die Köstlichkeit von Bonbon $i$ ($1 \le i \le N$) beträgt $A_i$.

JOI-kun hat beschlossen, einige der $N$ Bonbons auszuwählen und zu essen.

Um jedoch nicht zu viele Bonbons zu essen, isst er von jeweils $K$ aufeinanderfolgenden Bonbons höchstens $2$. Das heißt, für jedes $j$ ($1 \le j \le N - K + 1$) darf unter den $K$ aufeinanderfolgenden Bonbons von Bonbon $j$ bis Bonbon $j + K - 1$ die Anzahl der gegessenen Bonbons höchstens $2$ betragen.

Unter dieser Bedingung möchte JOI-kun die Summe der Köstlichkeiten der von ihm gegessenen Bonbons so groß wie möglich machen.

Schreibe ein Programm, das bei gegebener Köstlichkeit der $N$ Bonbons sowie $K$ den maximalen Wert der Summe der Köstlichkeiten der von JOI-kun gegessenen Bonbons berechnet.

Einschränkungen

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Alle Eingabewerte sind ganze Zahlen.

Teilaufgaben

1. ($4$ Punkte) $N \le 20$.
2. ($19$ Punkte) $K \le 10$.
3. ($47$ Punkte) $N \le 300$.
4. ($30$ Punkte) Keine weiteren Einschränkungen.

Eingabe

Die Eingabe erfolgt über die Standardeingabe im folgenden Format:

N K
A_1 A_2 ... A_N

Ausgabe

Gib auf der Standardausgabe in $1$ Zeile den maximalen Wert der Summe der Köstlichkeiten der von JOI-kun gegessenen Bonbons aus.

Beispiele

Beispiel-Eingabe 1

5 4
1 3 2 4 3

Beispiel-Ausgabe 1

8

Wenn JOI-kun Bonbon $1$, Bonbon $4$ und Bonbon $5$ isst, beträgt die Summe der Köstlichkeiten $8$.

Unter allen Auswahlmöglichkeiten, bei denen von jeweils $4$ aufeinanderfolgenden Bonbons höchstens $2$ gegessen werden, gibt es keine mit einer Gesamtköstlichkeit von $9$ oder mehr, daher wird $8$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Einschränkungen aller Teilaufgaben.

Beispiel-Eingabe 2

6 3
3 7 1 5 6 4

Beispiel-Ausgabe 2

21

Wenn JOI-kun Bonbon $1$, Bonbon $2$, Bonbon $4$ und Bonbon $5$ isst, beträgt die Summe der Köstlichkeiten $21$.

Unter allen Auswahlmöglichkeiten, bei denen von jeweils $3$ aufeinanderfolgenden Bonbons höchstens $2$ gegessen werden, gibt es keine mit einer Gesamtköstlichkeit von $22$ oder mehr, daher wird $21$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Einschränkungen aller Teilaufgaben.

Beispiel-Eingabe 3

5 2
3 3 2 2 1

Beispiel-Ausgabe 3

11

Dieses Eingabebeispiel erfüllt die Einschränkungen aller Teilaufgaben.

Beispiel-Eingabe 4

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

Beispiel-Ausgabe 4

4427122428

Dieses Eingabebeispiel erfüllt die Einschränkungen aller Teilaufgaben.