e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Культ-орки на сходах

Культ-орки на сходах

У Літній Кінематографічній Школі прийшов час обідати і ельф Коля поспішив у їдальню. Проте для того, щоб потрапити у їдальню, Колі потрібно піднятись по довгих сходах, а на кажній їх сходинці у цю пору доби стоїть по культорку. Кожен культорк дозволяє Колі пройти по своїй сходинці лише після того, як Коля запишеться на захід, який цей кульорк організовує. При цьому ніякі два культорки не проводять один і той самий захід, і усі заходи проходять у різний час.

Коля - чесний ельф, і якщо вже він запишеться на якусь гру чи конкурс, то потім обов'язково прийде прийняти участь. Проте Коля бажає витрачати якомога менше часу на розваги, адже інакше йому ніколи буде дорішувати кінематографічні задачки. На щастя, Колі не потрібно ступати на кожну сходинку, він може перестрибнути через декілька. Коля хоче взнати, яку мінімальну кількість часу йому прийдеться розпланувати за один прохід сходами до їдальні.

Вхідні дані

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

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5 2
7 3 9 2 11
Вихідні дані #1
14