Die Kühe wollen bessere Sportlerinnen werden. Bessie trainiert daher auf einer Laufbahn genau $N$ $(1 \le N \le 10,000)$ Minuten. Jede Minute läuft oder ruht sie die ganze Minute.

Die endgültige Strecke hängt vom „Erschöpfungsfaktor“ ab, anfangs 0. Beim Laufen in Minute $i$ läuft sie genau $D_i$ $(1 \le D_i \le 1,000)$ und der Faktor steigt um 1, darf jedoch nie $M$ $(1 \le M \le 500)$ überschreiten. Beim Ruhen sinkt er um 1 pro Minute. Erst bei 0 darf sie wieder laufen; dann kann sie laufen oder ruhen.

Nach $N$ Minuten muss Bessies Faktor genau 0 sein, sonst bleibt ihr zu wenig Kraft für den restlichen Tag.

Bestimme die größte mögliche Laufstrecke.

Eingabe

Lies von der Standardeingabe.

• Zeile 1: ganze Zahlen $N$ und $M$ mit Leerzeichen.
• Zeilen $2..N+1$: Zeile $i+1$ enthält nur die ganze Zahl $D_i$.

Ausgabe

Schreibe auf die Standardausgabe.

• Zeile 1: eine ganze Zahl, die größte Strecke unter den Bedingungen.

Beispiele

Eingabe 1

5 2
5
3
4
2
10

Ausgabe 1

9

Hinweis

Bessie läuft Minute 1 ($distance=5$), ruht Minute 2, läuft Minute 3 ($distance=4$), ruht Minute 4 und 5. In Minute 5 darf sie nicht laufen, da der Faktor am Ende nicht 0 wäre.

Autor: Neal Wu, 2007