Problem: Cloud Cover

Want to try solving this problem? You can submit your code online if you log in or register.

Cloud Coverage

Input File: cloudin.txt
Output File: cloudout.txt
Time Limit: 1 second
Memory Limit: 1 GB

During lunch you and your friends were playing your favourite game `stand along a line' when a huge cloud blew overhead. So you got to wondering, how long could that cloud have been? You immediately noted down how far apart each of your friends were standing from one another along the line, and the maximum number that were simultaneously underneath the cloud.

Note that if two people are exactly separated by the length of the cloud, then only one of them can be covered by the cloud at a time. Thus if a cloud is 5 metres long, and two people are standing 5 metres apart, the cloud is only able to cover one of them at a time.

You must now determine the maximum length the cloud could have been, taking into account the maximum number of people it covered simultaneously.

Input

The first line will contain the number of people standing along the line, N, followed by the maximum number covered at any time by the cloud K.

The following N-1 lines contain the successive distances between the N people playing the game. These will always be integers.

Output

The maximum length the cloud could have been given that it never covered more than K of your N friends.

Sample Input

Sample Output

Explanation

The absolute positions of people are given in the diagram above. A cloud of width 11 covers the last 3 people and never covers 4 people, specifically it doesn't cover the last 4 people completely at once.

Subtasks & Constraints

For all cases 1 ≤ K < N ≤ 100,000. Note that this means that 2 ≤ N. Further, let us call the distance between the first and last person in the line D. D ≤ 1,000,000,000. Finally, all distances between people will be at least 1.

For Subtask 1 (20 marks), D ≤ 500, N ≤ 100.
For Subtask 2 (10 marks), K = 1.
For Subtask 3 (10 marks), K = 2.
For Subtask 4 (20 marks), D ≤ 5,000, N ≤ 100.
For Subtask 5 (15 marks), N ≤ 5,000.
For Subtask 6 (25 marks), no further constraints apply.