Problems Base course RU

A balanced heading

binary search greedy text editors in production

A browser with text-wrap: balance evens out a heading like this. First it breaks the text greedily in a column of width W: as many words go into a line as fit. Suppose that gives k lines. Then it looks for the narrowest column in which the same greedy breaking gives no more than k lines, and sets the text in it: as many lines, but their lengths closer to each other.

Find the width of this narrowest column. Word i takes a_i characters, words in a line are separated by one space, and a line cannot be longer than the column.

Input

The first line holds n and W (1 ≤ n ≤ 5·10⁴, 1 ≤ W ≤ 10⁹). The second holds the n word lengths (1 ≤ a_i ≤ min(W, 10⁴)).

Output

A single number: the smallest column width in which greedy breaking gives no more than k lines.

The first example is the Russian heading «Как разбить абзац на строки так, чтобы правый край был ровным» (“How to break a paragraph into lines so that the right edge is even”) in a column of 30 characters. Greedily it comes to three lines, the last being the single word «ровным». In a column of 22 characters there are also three lines, «Как разбить абзац на / строки так, чтобы / правый край был ровным», while in a column of 21 there are already four.

Examples

Example 1

Input

11 30
3 7 5 2 6 4 5 6 4 3 6

Output

Example 2

Input

3 20
10 15 5

Output

Limits

Time · Python: 6000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Can greedy breaking give more lines in a wider column than in a narrower one?

2The idea

It cannot. Greedy breaking gives the smallest possible number of lines at a given width, as proved in the article. And any breaking that fits in a narrow column fits in a wide one, so the smallest number of lines does not grow as the width grows. So the condition “greedily no more than k lines” is monotone in the width: if it holds at w, it holds at any greater width. The narrowest such width is found by binary search on the answer.

3Walkthrough

Compute k, the number of lines of greedy breaking at width W. Search for the answer on the range from the longest word (in a narrower column it will not fit) to W (where the condition holds). At each step check the middle with one greedy pass. This is just what Chromium does: according to the description on the Chrome developers’ blog, it uses binary search to find the narrowest width that does not add lines.

3+Solution

4Complexity

One greedy pass is O(n), and there are O(log W) passes, about 30: O(n log W) in all.

5Common mistakes

Dividing equally. The length of the text divided by k is a lower bound, but words are not cut, and at that width greedy breaking often gives an extra line. The first example: dividing equally gives 21, but 22 is needed.
Searching below the longest word. There the line with that word fits in no column; with the right lower bound this case does not arise.
Trying widths one character at a time. The answer is the same, but with W up to 10⁹ that is a billion greedy passes.

Algorithms behind it

DP Algorithm Beautiful line breaking Greedy breaking against the whole paragraph at once: a shortest path through the break points, as in TeX. O(n·L) 2 problems SRT Technique Binary search on the answer If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving. O(log D · cost of a check) 2 problems PAR Technique Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 2 problems