eolymp
bolt
Try our new interface for solving problems

Queue

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~(1 \le n \le 10^5, 1 \le k \le 10^4). n positive integers are given in the second line. The i-th number gives the time t_i~(1 \le t_i \le 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.

Examples

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