103193: [Atcoder]ABC319 D - Minimum Width

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

问题描述

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

单词在窗口中用宽度为 $1$ 的空格隔开。 更准确地说，当句子在一个宽度为 $W$ 的窗口中显示时，满足以下条件。

• 句子被分为多行。
• 第一个单词显示在顶部行的开头。
• 第 $i$ 个单词 $(2\leq i\leq N)$ 要么在第 $(i-1)$ 个单词之后空格 $1$ 的位置显示，要么在包含第 $(i-1)$ 个单词的行的下一行的开头显示。它不会在其他任何地方显示。
• 每行的宽度不超过 $W$。这里，行的宽度指的是左起始单词到右起始单词的距离。

当高桥在窗口中显示句子时，句子可以放在 $M$ 行或更少的行中。 找到窗口的最小可能宽度。

限制条件

• $1\leq M\leq N\leq2\times10 ^ 5$
• $1\leq L _ i\leq10^9\ (1\leq i\leq N)$
• 所有的输入值都是整数。

输入

输入从标准输入按以下格式给出：

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

输出

在一行中打印答案。

样例输入 1

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

样例输出 1

26

当窗口的宽度为 $26$ 时，你可以将给定的句子放入三行中，如下所示。

当窗口的宽度为 $25$ 或更少时，无法将给定的句子放入三行中，因此打印 $26$。

请注意，你不应跨多行显示单词，让行的宽度超过窗口的宽度，或重新排列单词。

样例输入 2

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

样例输出 2

10000000009

请注意，答案可能无法放入一个 $32\operatorname{bit}$ 整数中。

样例输入 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

样例输出 3

189