Queue Data Structure


Time limit 1 second
Memory limit 128 MiB

In civilized countries k ticket offices are working at the train station, but the queue to them is just one. The service works as follows. Initially, when all the ticket offices are free, the first k people from the queue go to the offices. The others are waiting their turn. As soon as someone is served and the corresponding office becomes free, the next person in the queue comes to this office. This continues until all the people will be served.

Find the time to serve all the clients.

Input data

The first line contains two integers: the queue size n and the number of ticket offices k (1n10^5, 1k10^4). n positive integers are given in the second line. The i-th number gives the time t[i] (1t[i]10^5) to serve the i-th client in the queue.

Output data

Print one integer - the time to serve all the people in the queue.


Input example #1
5 2
3 1 1 2 3
Output example #1
Input example #2
7 3
1 2 3 4 5 3 1
Output example #2
Author Неспирный В.Н.
Source III этап УОИ Донецк, 2012 г. I тур 10-11 кл.