You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小Z想要在窗口中显示由(N)个单词组成的文章。所有单词的纵宽都相等，第(i)个（(1\leq i\leq N)）单词的横宽为(L_i)。

文章在窗口中显示时，以横宽为(1)的空白作为单词的分隔。更确切地说，当小Z在横宽为(W)的窗口中显示文章时，满足以下条件：

• 文章被分成若干行。
• 第(1)个单词显示在最上面一行的开头。
• 第(i)个（(2\leq i\leq N)）单词，要么在第(i - 1)个单词之后间隔(1)显示，要么显示在包含第(i - 1)个单词的那一行的下一行的开头，不存在其他的显示位置。
• 每一行的横宽不超过(W)。这里，行的横宽是指从最左边的单词的左端到最右边的单词的右端的距离。

当小Z把文章显示在窗口中时，文章刚好能在(M)行内显示完。请求出窗口横宽可能的最小值。 い。

输入格式

第一行包含三个整数(N)和(M)。 第二行包含(N)个整数，第(i)个整数是(L_i)。

输出格式

输出一个整数，表示窗口横宽可能的最小值。

输入输出样例 #1

输入 #1

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

输出 #1

26

输入输出样例 #2

输入 #2

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

输出 #2

189

说明/提示

限制条件

• (1\leq M\leq N\leq2\times10^5)
• (1\leq L_i\leq10^9\ (1\leq i\leq N))
• 输入的所有值均为整数

Sample Explanation 1

总和是9+5+2+7+1+8+8+2+1+5+2+3+6 = 59，加上12个空格，共71，当窗口宽度为26时，可以按照如下方式将给定的文章收纳在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）. 所以w=26是满足要求的最小值。