e-olymp
Задачі

Черга

Черга

У цивілізованих країнах на залізничному вокзалі працює k кас, проте черга до них всього одна. Обслуговування відбувається наступним чином. Спочатку, коли усі каси вільні, перші k чоловік з черги підходять до кас. Інші чекають своєї черги. Як тільки кого-небудь буде обслужено і відповідна каса звільниться, наступна людина з черги підходить до цієї каси. Так продовжується до тих пір, доки не буде обслужено усіх клієнтів.

Визначте час, за який буде обслужено усіх клієнтів.

Вхідні дані

У першому рядку знаходиться два цілих числа: розмір черги n та кількість кас k (1n105, 1k104). У другому рядку задано n натуральних чисел. i-те число визначає час ti (1ti105), який потрібно для того, щоб обслужити i-го клієнта з черги.

Вихідні дані

Виведіть одне число - час, за який буде обслужено задану чергу.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5 2
3 1 1 2 3
Вихідні дані #1
6
Вхідні дані #2
7 3
1 2 3 4 5 3 1
Вихідні дані #2
7
Автор Неспірний В.М.
Джерело III этап УОИ Донецк, 2012 г. I тур 10-11 кл.