Implementation: Data Structures


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.


The first line contains two integers: the queue size n and the number of ticket offices k (1n105, 1k104). n positive integers are given in the second line. The i-th number gives the time ti (1ti105) to serve the i-th client in the queue.


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

Time limit 1 second
Memory limit 128 MiB
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 кл.