Le mucche vogliono essere atlete migliori, così Bessie si allena su una pista per esattamente $N$ $(1 \le N \le 10,000)$ minuti. Ogni minuto sceglie di correre o riposare per tutto il minuto.

La distanza finale dipende dal «fattore di stanchezza», inizialmente 0. Correndo nel minuto $i$ percorre esattamente $D_i$ $(1 \le D_i \le 1,000)$ e il fattore cresce di 1, ma non deve mai superare $M$ $(1 \le M \le 500)$. Riposando cala di 1 al minuto. Non può riprendere a correre finché non raggiunge 0; allora può correre o riposare.

Al termine dei $N$ minuti il fattore di Bessie deve essere esattamente 0, o non resterà energia per il resto della giornata.

Trova la massima distanza percorribile.

Input

Leggi dallo standard input.

• Riga 1: interi $N$ e $M$ separati da spazio.
• Righe $2..N+1$: la riga $i+1$ contiene il solo intero $D_i$.

Output

Scrivi sullo standard output.

• Riga 1: un intero con la massima distanza che rispetta le condizioni.

Esempi

Input 1

5 2
5
3
4
2
10

Output 1

9

Spiegazione

Bessie corre nel primo minuto ($distance=5$), riposa nel secondo, corre nel terzo ($distance=4$), riposa nel quarto e quinto. Non può correre nel quinto perché non finirebbe con fattore 0.

Autore: Neal Wu, 2007