Задачи
Очередь
Очередь
В цивилизованных странах на железнодорожном вокзале работают $k$ касс, однако очередь в них всего одна. Обслуживание происходит следующим образом. Изначально, когда все кассы свободны, первые $k$ человек из очереди подходят к кассам. Остальные ждут своей очереди. Как только кто-нибудь будет обслужен и соответствующая касса освободится, следующий человек из очереди подходит к этой кассе. Так продолжается до тех пор, пока не будут обслужены все клиенты.
Определите время, за которое будут обслужены все клиенты.
\InputFile
В первой строке находится два целых числа: размер очереди $n$ и количество касс $k~(1 \le n \le 10^5, 1 \le k \le 10^4)$. Во второй строке задаются $n$ натуральных чисел. $i$-ое число определяет время $t_i~(1 \le t_i \le 10^5)$, которое требуется для того, чтобы обслужить $i$-го клиента из очереди.
\OutputFile
Выведите одно число --- время, за которое будет обслужена заданная очередь.
Входные данные #1
5 2 3 1 1 2 3
Выходные данные #1
6
Входные данные #2
7 3 1 2 3 4 5 3 1
Выходные данные #2
7