分数: 400 点
问题陈述
高桥正在显示一个句子 N 窗口中的文字。 所有单词的高度和宽度都相同 i- 第一个字 (1\leq i\leq N) is L _ i.
单词显示在窗口中,并以宽度间隔分隔 1。 更准确地说,当句子显示在宽度的窗口中时 W,满足以下条件。
- 该句子分为几行。
- 第一个单词显示在顶行的开头。 显示
- 的 i- 第一个字 (2\leq i\leq N) ,间隙为 1 之后 (i-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