描述

届时，牧草将被有顺序的分成了\( n \)组，\(m\)只奶牛于是排好队伍，按顺序等待Smart先生发放若干组牧草给自己，按照规则，奶牛们得到的牧草的分组编号一定是连续的，由于每组牧草的草量并非都一样，每只奶牛得到的牧草组数也未必一样，所以，这必将会造成一定程度上的不公平，Smart先生希望尽量维护这种公平，于是他想到了一个方法：让得到牧草最多的那只奶牛的牧草尽可能的少。
举个例子，假如牧草有\(5\)组，奶牛有两只……
每组牧草的草量分别为：\(1,2,3,4,5\)
于是，最佳的分配方案就是\(（1，2，3）（4，5）\)
这样，得到最多牧草的奶牛拥有的牧草是\(4+5=9\),是我们所期待的最小的值。

格式

输入格式

第一行，\(2\)个整数，\(n、m\)，
第二行，\(n\)个整数，表示每组牧草的含草量。

输出格式

一个整数，即：最佳分配方案下，拥有草最多的那只奶牛的有草量。

样例1

样例输入1

5 2
1 2 3 4 5

样例输出1

9

限制

\(100\%\)的数据：\(n≤2000000\)。