Коровы хотят стать лучшими спортсменками, поэтому Bessie тренируется на дорожке ровно $N$ $(1 \le N \le 10,000)$ минут. Каждую минуту она выбирает бег или отдых на всю минуту.

Итоговое расстояние зависит от «коэффициента усталости», изначально равного 0. При беге в минуту $i$ она пробегает ровно $D_i$ $(1 \le D_i \le 1,000)$, а коэффициент растёт на 1, но никогда не должен превышать $M$ $(1 \le M \le 500)$. При отдыхе он уменьшается на 1 за минуту. Снова начать бежать можно лишь после достижения 0; тогда можно бежать или отдыхать.

В конце тренировки длиной $N$ минут коэффициент Bessie должен быть ровно 0, иначе на остаток дня не хватит сил.

Найдите максимальное расстояние.

Входные данные

Читайте из стандартного ввода.

• Строка 1: целые $N$ и $M$ через пробел.
• Строки $2..N+1$: строка $i+1$ содержит одно целое $D_i$.

Выходные данные

Пишите в стандартный вывод.

• Строка 1: одно целое — наибольшее расстояние при соблюдении условий.

Примеры

Входные данные 1

5 2
5
3
4
2
10

Выходные данные 1

9

Примечание

Bessie бежит первую минуту ($distance=5$), отдыхает вторую, бежит третью ($distance=4$), отдыхает четвёртую и пятую. В пятую бежать нельзя: в конце усталость не будет 0.

Автор: Neal Wu, 2007