小明的显示器在一个窗口中显示一个包含 N 个单词的句子。所有单词的均占一个单位的高度，而第 i(1\le i\le N) 个单词的字数为 L _ i。

单词显示在窗口中，中间要用 1 个空格隔开。更确切地说，当句子显示在字数为 W 的窗口中时，需要满足以下条件。

- 句子被分成的行数要 \le M。

- 第一个单词显示在第一行的开头。

- 第 i 个单词后要隔一个空格，最后一个不需要。

- 每行的字数不超过 W。这里，一行的字数指的是从最左侧单词的左端到最右侧单词的右端之间的距离，空格算一个字。

两个数字，N和M，分别表示单词数量和能显示的行数

N个单词的长度Li。

屏幕的一行最少需要多少长！

- 30%的数据： 1\leq\ M\leq\ N\leq2\times10^3

- 100%的数据： 1\leq\ M\leq\ N\leq2\times10^5

- 1\leq\ L\ _\ i\leq10^9\ (1\leq\ i\leq\ N)