Score : $400$ points

问题描述

高桥在窗口中展示一个包含 $N$ 个单词的句子。所有单词高度相同，第 $i$ 个单词 $(1\leq i\leq N)$ 的宽度为 $L_i$。

单词在窗口中以宽度为 $1$ 的空格分隔显示。更具体地说，当这个句子在宽度为 $W$ 的窗口中显示时，满足以下条件：

• 句子被分成若干行。
• 第一个单词从第一行的起始位置开始显示。
• 第 $i$ 个单词 $(2\leq i\leq N)$ 要么在第 $(i-1)$ 个单词后面留有 $1$ 个空格的间隔，要么在包含第 $(i-1)$ 个单词的下一行的起始位置开始显示。它不会显示在其他任何地方。
• 每行的宽度不超过 $W$。这里，行的宽度指的是从最左边单词左端到最右边单词右端的距离。

当高桥在窗口中展示这个句子时，该句子恰好能容纳在 $M$ 行或更少的行内。请找出窗口可能的最小宽度。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi is displaying a sentence with $N$ words in a window. All words have the same height, and the width of the $i$-th word $(1\leq i\leq N)$ is $L _ i$.

The words are displayed in the window separated by a space of width $1$. More precisely, when the sentence is displayed in a window of width $W$, the following conditions are satisfied.

• The sentence is divided into several lines.
• The first word is displayed at the beginning of the top line.
• The $i$-th word $(2\leq i\leq N)$ is displayed either with a gap of $1$ after the $(i-1)$-th word, or at the beginning of the line below the line containing the $(i-1)$-th word. It will not be displayed anywhere else.
• The width of each line does not exceed $W$. Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.

When Takahashi displayed the sentence in the window, the sentence fit into $M$ or fewer lines. Find the minimum possible width of the window.

Constraints

• $1\leq M\leq N\leq2\times10 ^ 5$
• $1\leq L _ i\leq10^9\ (1\leq i\leq N)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$L _ 1$ $L _ 2$ $\ldots$ $L _ N$

Output

Print the answer in one line.

Sample Input 1

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

Sample Output 1

26

When the width of the window is $26$, you can fit the given sentence into three lines as follows.

You cannot fit the given sentence into three lines when the width of the window is $25$ or less, so print $26$.

Note that you should not display a word across multiple lines, let the width of a line exceed the width of the window, or rearrange the words.

Sample Input 2

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

10000000009

Note that the answer may not fit into a $32\operatorname{bit}$ integer.

Sample Input 3

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

Sample Output 3

189

update @ 2024/3/10 09:07:20