Picture Caption

The UCF Programming Team Lab (PTL) is located in HEC. The team photos are posted outside this lab. When preparing the caption for a picture, there is always the question of how many names should be listed on each line under the picture.

Given the number of names, number of lines to use for the picture caption, and number of letters in each name, we would like to minimize the length of the longest line in the caption.

Note that the names must appear in the caption in the order of the input, i.e., we don’t want to reorder the names. Also note the following common constraints:

• No space before the first name on each caption line.
• No space after the last name on each caption line.
• Exactly one space between two consecutive names on each caption line.

The first input line contains two integers n and k (1 ≤ k ≤ n ≤ 105), indicating (respectively) the number of names and the number of lines to use for the picture caption.

The second input line contains n integers ci (1 ≤ ci ≤ 104), representing the number of letters in each name in order.

Print the length of the longest line in the caption, keeping in mind that we would like to minimize this value.