AT_abc319_d [ABC319D] Minimum Width

高桥君想要将由 $N$ 个单词组成的句子显示在窗口中。所有单词的纵向高度相同，第 $i$ 个单词（$1 \leq i \leq N$）的横向宽度为 $L_i$。 句子在窗口中显示时，单词之间用宽度为 $1$ 的空格分隔。更严格地说，当高桥君在宽度为 $W$ 的窗口中显示句子时，需满足以下条件： - 句子被分成若干行显示。 - 第 $1$ 个单词显示在最上面一行的开头。 - 第 $i$ 个单词（$2 \leq i \leq N$）要么紧跟在第 $i-1$ 个单词后面，中间隔一个空格，要么显示在第 $i-1$ 个单词所在行的下一行的开头。除此之外不能出现在其他位置。 - 每一行的横向宽度不能超过 $W$。这里，行的宽度指的是从最左侧单词的左端到最右侧单词的右端的距离。 当高桥君将句子显示在窗口中时，句子正好被分成了 $M$ 行。请你求出可能的最小窗口宽度 $W$。

输入以如下格式从标准输入给出。 > $N$ $M$ $L_1$ $L_2$ $\ldots$ $L_N$

请输出一个整数，表示可能的最小窗口宽度 $W$。

## 限制条件 - $1 \leq M \leq N \leq 2 \times 10^5$ - $1 \leq L_i \leq 10^9$（$1 \leq i \leq N$） - 输入均为整数 ## 样例解释 1 当窗口宽度为 $26$ 时，可以如下图所示将给定的句子分成 $3$ 行显示。  当窗口宽度小于等于 $25$ 时，无法将句子分成 $3$ 行显示，因此应输出 $26$。 注意，不能将单词跨行显示，不能使行宽超过窗口宽度，也不能改变单词顺序。  ## 样例解释 2 请注意，答案可能超出 $32$ 位整数的范围。 由 ChatGPT 4.1 翻译