Krowy chcą być lepszymi sportsmenkami, więc Bessie ćwiczy na bieżni dokładnie $N$ $(1 \le N \le 10,000)$ minut. W każdej minucie biegnie lub odpoczywa przez całą minutę.

Ostateczny dystans zależy od „współczynnika zmęczenia”, początkowo 0. Biegnąc w minucie $i$ pokonuje dokładnie $D_i$ $(1 \le D_i \le 1,000)$, a współczynnik rośnie o 1, lecz nigdy nie może przekroczyć $M$ $(1 \le M \le 500)$. Odpoczynek zmniejsza go o 1 na minutę. Nie może znów zacząć biec, dopóki nie osiągnie 0; wtedy może biec lub odpoczywać.

Po $N$ minutach współczynnik Bessie musi być dokładnie 0, inaczej zabraknie sił na resztę dnia.

Znajdź największy możliwy dystans.

Wejście

Czytaj ze standardowego wejścia.

• Wiersz 1: całkowite $N$ i $M$ rozdzielone spacją.
• Wiersze $2..N+1$: wiersz $i+1$ zawiera jedną całkowitą $D_i$.

Wyjście

Pisz na standardowe wyjście.

• Wiersz 1: jedna całkowita, największy dystans spełniający warunki.

Przykład

Wejście 1

5 2
5
3
4
2
10

Wyjście 1

9

Uwagi

Bessie biegnie w minucie 1 ($distance=5$), odpoczywa w 2, biegnie w 3 ($distance=4$), odpoczywa w 4 i 5. W 5 nie może biec, bo końcowe zmęczenie nie byłoby 0.

Autor: Neal Wu, 2007