Бег
Коровы хотят стать лучшими спортсменами, поэтому Бесси бежит по дорожке ровно n минут. Каждую минуту она может либо бежать, либо отдыхать целую минуту.
Однако максимальное расстояние, которое пробегает Бесси, зависит от ее фактора истощения, который начинается с 0. Если она решает бежать в минуту i, то пробежит расстояние в точности d[i], а ее коэффициент истощения увеличится на 1 (однако он никогда не должен превышать m). Если Бесси решит отдохнуть, то ее фактор истощения уменьшается на 1 за каждую минуту отдыха. Она не может снова начать бег, пока ее фактор истощения не достигнет 0. В этот момент она может выбрать что делать - бежать или отдыхать.
В конце n-ой минуты тренировки коэффициент истощения Бесси должен равняться 0, иначе у нее не останется энергии на остаток дня.
Найдите максимальное расстояние, которое может пробежать Бесси.
Входные данные
Первая строка содержит два целых числа n (1 ≤ n ≤ 10^4) и m (1 ≤ m ≤ 500). Следующие n строк содержат целые числа d[1], d[2], ..., d[n] (1 ≤ d[i] ≤ 1000).
Выходные данные
Выведите единственное целое число, представляющее наибольшее расстояние, которое Бесси может пробежать при соблюдении условий.