该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

农民约翰是一个惊人的会计，并意识到自己可能遇到了农场的资金周转不灵时期。他已经计算和记录了N天（1≤N≤100000）每一天需要花费资金的确切数额（1≤moneyi≤10000）。

由于每天向别人支付花费是一件非常麻烦的事情，所以聪明的约翰把连续的几天打包成一个集合，最多Ｍ(1≤M≤N)个集合，每个集合付一次钱。这样就可以减少付钱的次数，当然总数是不变的。

对于每种分配方式，存在一个评价系数level，level为每一次付出费用的最大值。当然了，level的值越小，约翰会越有成就感。你的任务是帮助约翰计算出这个最小值。

输入格式

第一行输入两个整数N和M

接下来按顺序输入每一天需要花费资金的数额。

输出格式

输出level的最小值。

样例

7 5
100
400
300
100
500
101
400

500