Picture Caption

Interview

Time limit1sMemory limit1024 MB

Summary

Split n names, in fixed order, into k consecutive lines so the longest line (letters plus single spaces between names) is as short as possible, and print that minimum length.

Level: Medium4 of 10
Topics: Binary search, Greedy, Prefix sum
Solved: No attempts yet

Problem

The UCF Programming Team Lab (PTL) is in HEC. Team photos are posted outside the lab. When writing a caption for a picture, you must decide how many names go on each line below the picture.

Given the number of names, the number of lines for the caption, and the number of letters in each name, minimize the length of the longest line in the caption.

The names must appear in the caption in the order of the input. You may not reorder them. The following rules also apply:

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

Input

The first line contains two integers $n$ and $k$ ( $1 \le k \le n \le 10^5$ ), the number of names and the number of lines to use for the caption.

The second line contains $n$ integers $c_i$ ( $1 \le c_i \le 10^4$ ), the number of letters in each name, in order.

Output

Print the length of the longest line in the caption when this length is minimized.

Examples3

Example 1
Input
```
7 4
1 2 8 3 5 2 7
```
Expected output
```
10
```
Example 2
Input
```
7 5
1 2 8 3 5 2 7
```
Expected output
```
8
```
Example 3
Input
```
7 2
3 1 1 3 9 5 2
```
Expected output
```
18
```