Guitar Lesson

An instructor wants to record guitar lecture videos onto several Blu-ray discs in order. The lectures must be recorded in their original order, because changing the order would break the flow of the course. Therefore, if lecture i and lecture j are recorded on the same disc, every lecture between them must also be recorded on that same disc.

The instructor has decided to store all lectures on exactly M Blu-ray discs. Every disc must have the same capacity, and each lecture must fit entirely on one disc. Find the minimum possible disc capacity.

The first line contains the number of lectures N and the number of Blu-ray discs M. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

The second line contains the lecture lengths in order, measured in minutes as positive integers. Each lecture length is at most 10,000 minutes.

Print the minimum possible Blu-ray capacity on the first line.

Consider the case with 9 lectures and 3 discs. If lectures 1 through 5 go on the first disc, lectures 6 and 7 on the second disc, and lectures 8 and 9 on the third disc, the total lengths are 15, 13, and 17. Since every disc must have the same capacity, the required capacity is 17, and no smaller capacity can store all lectures.