e-olymp
Problems

Культ-орки на лестнице

Культ-орки на лестнице

В Летней Кинематографической Школе пришло время обеда и эльф Коля поспешил в столовую. Однако для того, чтобы попасть в столовую, Коле нужно подняться по длинной лестнице, а на каждой её ступеньке в это время суток стоит по культорку. Каждый культорк разрешает Коле пройти по своей ступеньке только после того, как Коля запишется на мероприятие, которое этот кульорк организует. При этом никакие два культорка не проводят одно и то же мероприятие, и все мероприятия проходят в разное время.

Коля - честный эльф, и если уж он запишется на какую игру или конкурс, то потом обязательно придёт поучаствовать. Однако Коля хочет тратить как можно меньше времени на развлечения, ведь иначе ему некогда будет дорешивать кинематографические задачки. К счастью, Коле не надо наступать на каждую ступеньку, он может перепрыгнуть через несколько. Коля хочет узнать, какое минимальное количество времени ему придётся распланировать за один проход по лестнице до столовой.

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

В первой строке вводятся два числа n и k (1n10000, 0k20). n - количество ступенек на лестнице. k - максимальное количество ступенек, через которые Коля может перепрыгнуть за один прыжок (то есть, например, на первом шаге Коля может прыгнуть на (k + 1)-ую или более низкие ступеньки). Во второй строке вводятся n чисел: i-ое число указывает на длительность в минутах того меропртия, которое проведёт культорк, стоящий на i-ой ступеньке. Каждое мероприятие не может длиться более 24 часов. Ступеньки нумеруются снизу вверх, ступенькой номер n считается весь этаж столовой.

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

Выведите одно число - минимальное количество минут, которое Коле придётся распланировать.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 2
7 3 9 2 11
Output example #1
14