2019编程导论 第二次月考

E. 附加题

单点时限: 1.0 sec

内存限制: 512 MB

小L是一个货物搬运工,这一天他需要从n辆货车上将货物运送到不同的地点。一辆车上有ai个货物,由于一辆车上的货物都是需要搬运到同一个地点,因此小L只能先搬运完一辆货车上的所有货物,才能到下一辆货车继续搬运其他的货物。小L希望能有更多的时间去休闲娱乐,因此他想最多搬运k次货物就能把所有的货物运送完毕。但是由于货物比较重,小L不希望一次性搬很多的货物,小L想知道在每天最多搬运k次货物的情况下,一次搬运货物的最大数量的最小值是多少?

输入格式

第一行包含两个正整数n, k,分别表示当天货车的数量和一天最多搬运k次货物。(1<=n<=105,n<=k<=109)

第二行包含n个正整数ai,表示第i辆货车上有ai个货物。(1<=ai<=105)

输出格式

输出小L一次搬运货物的最大数量的最小值是多少

样例

Input
3 6
7 4 10
Output
4