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.
The following N-1 lines contain the successive distances between the N people playing the game. These will always be integers.
6 3 3 6 4 2 5
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.