题目描述

小慧把她学会的英文单词记录了下来，现在她希望在一个文本框里完全显示出她记录的单词库。已知这个文本框最多只能显示 $M$ 行，小慧的单词库有 $N$ 个单词，要求按原次序显示所有单词，每个单词至少要用一个空格分开，而且一个单词的所有字母必须放在同一行。问这个文本框至少需要多宽才能满足小慧的需求。

输入格式

第一行包含两个正整数 $N$ 和 $M$。 第二行包含 $N$ 个正整数，表示每个单词的长度。

输出格式

输出一个整数，表示能把所有单词显示出来的文本框的最少宽度。

样例

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

26

提示

单词序列为：9, 5, 2, 7, 1, 8, 8, 2, 1, 5, 2, 3, 6，共 $13$ 个单词，分成 $3$ 行显示。 最优分行方案之一为：

• 第一行：9 5 2 7 (总长度 9+1+5+1+2+1+7=26，含空格)
• 第二行：1 8 8 2 1 (总长度 1+1+8+1+8+1+2+1+1=24)
• 第三行：5 2 3 6 (总长度 5+1+2+1+3+1+6=19)

文本框宽度需不小于最长行的总长度 $26$，故最少宽度为 $26$。

数据范围

• 对于 $40\%$ 的数据：$1 \le N, M \le 10^3$，每个单词的长度 $\le 10^2$
• 对于 $100\%$ 的数据：$1 \le N, M \le 2 \times 10^5$，每个单词的长度 $\le 10^9$