Коровы хотят стать лучшими спортсменами, поэтому Бесси бежит по дорожке ровно n минут. Каждую минуту она может либо бежать, либо отдыхать целую минуту.

Однако максимальное расстояние, которое пробегает Бесси, зависит от ее фактора истощения, который начинается с 0. Если она решает бежать в минуту i, то пробежит расстояние в точности di, а ее коэффициент истощения увеличится на 1 (однако он никогда не должен превышать m). Если Бесси решит отдохнуть, то ее фактор истощения уменьшается на 1 за каждую минуту отдыха. Она не может снова начать бег, пока ее фактор истощения не достигнет 0. В этот момент она может выбрать что делать - бежать или отдыхать.

В конце n-ой минуты тренировки коэффициент истощения Бесси должен равняться 0, иначе у нее не останется энергии на остаток дня.

Найдите максимальное расстояние, которое может пробежать Бесси.

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

Первая строка содержит два целых числа n (1 ≤ n ≤ 104) и m (1 ≤ m ≤ 500). Следующие n строк содержат целые числа d1, d2, ..., dn (1 ≤ di ≤ 1000).

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

Выведите единственное целое число, представляющее наибольшее расстояние, которое Бесси может пробежать при соблюдении условий.