描述

届时，牧草将被有顺序的分成了$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$。