最小宽度

题目描述

Takahashi 正在一个窗口中显示由 $N$ 个单词组成的句子。 所有单词高度相同,第 $i$ 个单词 $(1 \le i \le N)$ 的宽度为 $L_i$。

窗口中,单词之间以宽度为 $1$ 的空格分隔显示。 更准确地说,当句子显示在宽度为 $W$ 的窗口中时,满足以下条件:

• 句子被分成若干行。
• 第一个单词显示在最上面一行的开头。
• 第 $i$ 个单词 $(2 \le i \le N)$ 显示在第 $i-1$ 个单词之后间隔 $1$ 的位置,或者显示在包含第 $i-1$ 个单词的行的下一行开头。它不会被显示在其他位置。
• 每一行的宽度不超过 $W$。这里,行的宽度指从最左单词的左端到最右单词右端的距离。

当 Takahashi 在窗口中显示这个句子时,句子被排成了不超过 $M$ 行。 求窗口的最小可能宽度。

输入格式

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

$N$ $M$
$L_1$ $L_2$ $\ldots$ $L_N$

输出格式

以一行输出答案。

样例

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

26

当窗口宽度为 $26$ 时,可以将给定句子排成三行。

当窗口宽度为 $25$ 或更小时无法将给定句子排成三行,因此输出 $26$。

注意,不能将单词拆到多行中,不能使行宽超过窗口宽度,也不能重新排列单词的顺序。

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

10000000009

注意答案可能超出 $32$ 位整数范围。

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

189

数据范围

• $1 \le M \le N \le 2 \times 10^5$
• $1 \le L_i \le 10^9\ (1 \le i \le N)$
• 所有输入值均为整数。