题目描述

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

输入格式

第一行，两个正整数 $N，M$。

第二行，$N$ 个正整数，表示每个单词的长度。

输出格式

能把所有单词显示出来的文本框的最少宽度。

样例

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

26

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

数据范围

对于 40% 的数据，$1 \le N,M \le 10^3$，每个单词的长度 $\le 10^2$。

对于 100% 的数据，$1 \le N,M \le 2*10^5$，每个单词的长度 $\le 10^9$。