又到了严酷的夏日，这是电厂老板狗头吕每年最头痛的时候。

因为用电负载量过大，经常导致电线gg，这个时候就需要派遣电工去进行修理。

一天，又有一条电线gg了。由于电线是一段一段的，吕老板已经确定了有连续的 m 段出现了损坏，于是他派出 k 个工人去修理。

考虑到工人们不想来回跑，所以要给每个工人分配一个连续的修复区间。

工人的修复区间不能有重合，否则他们会偷懒。

现请你帮助吕老板，来尽快修复电线，每个工人的修复速度都是一样的，修复所有损坏段后才算完成。

多组数据

第一行两个第一行两个整数 m，k；( 1 <= k, m <= 100000)

第二行m个整数，Ti ，分别表示修理第 i 段电线所需时间。(1 <= Ti <= 1000)

每组数据一行，一个整数，即修复电线的最少用时。

样例，第一个工人修1 2 3 4 5，用时15

第二个工人修 6 7，用时 13

第三个工人修 8 9，用时 17

所以 17 时间后才能修完