题目描述

Lily 是一个外文网络小说作家，有一次她写完一段英文句子之后，电脑被病毒入侵了，Lily 立马进行了杀毒措施，虽然文档还存在，但是这段单词的排版出现了问题，Lily 需要重新进行排版，具体要求如下。

每个单词要显示在创作窗口内，中间以 $1$ 个空格隔开，当每行的字数限制在 $W$ 以内时，需要满足以下要求：

• 句子被分成的行数要 $≤M$。
• 第一个单词显示在第一行的开头。
• 第 $i$ 个单词后要隔一个空格，最后一个不需要。
• 每行的字数不超过 $W$。这里，一行的字数指的是从最左侧单词的左端到最右侧单词的右端之间的距离，空格算一个字。

注意：换行时需要保证每个单词不跨两行。

请根据输入的信息算一算这段话每行最多可以摆放多少个字符。

输入格式

第一行，两个整数，表示 $N$ 和 $M$。$1≤M≤N≤2×10^5$。

第二行，$N$ 个整数 $L_i$，表示每个单词的长度。$1≤L​i≤10^9$。

输出格式

一行，一个整数，表示这段话每行最多可以摆放多少个字符。

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

26

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

10000000009

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