Les vaches veulent devenir de meilleures athlètes : Bessie s'entraîne sur une piste pendant exactement $N$ $(1 \le N \le 10,000)$ minutes. Chaque minute, elle court ou se repose durant toute la minute.

La distance finale dépend de son « facteur de fatigue », initialement 0. Courir à la minute $i$ donne exactement $D_i$ $(1 \le D_i \le 1,000)$ de distance et augmente la fatigue de 1, sans jamais dépasser $M$ $(1 \le M \le 500)$. Le repos la réduit de 1 par minute. Elle ne peut reprendre la course avant que la fatigue atteigne 0 ; alors elle peut courir ou se reposer.

Au bout des $N$ minutes, sa fatigue doit être exactement 0, sinon il ne lui restera pas assez d'énergie pour la journée.

Trouvez la distance maximale parcourable.

Entrée

Lisez sur l’entrée standard.

• Ligne 1 : entiers $N$ et $M$ séparés par un espace.
• Lignes $2..N+1$ : la ligne $i+1$ contient l'entier unique $D_i$.

Sortie

Écrivez sur la sortie standard.

• Ligne 1 : un entier donnant la distance maximale respectant les conditions.

Exemples

Entrée 1

5 2
5
3
4
2
10

Sortie 1

9

Remarque

Bessie court la première minute ($distance=5$), se repose la deuxième, court la troisième ($distance=4$), se repose les quatrième et cinquième. Elle ne peut courir la cinquième car sa fatigue finale ne serait pas 0.

Auteur : Neal Wu, 2007