1594: 吃萝卜(eat)
题目描述
在一个神奇的国度里，有一只编程兔，它每天都写很多的代码，各种编程语言如pascal、c、c++、java、basic等等它都了如指掌，各种算法也都已经滚瓜乱熟了。小花是它的好朋友，经常和它一起玩耍。
某一天，小花给编程兔送来了很多的萝卜。编程兔很开心，决定把它的萝卜和其它的小兔子一起分享。小花共计送来了n袋萝卜（编号1到n），每袋里面都有一定数量的萝卜。小兔子共计有m只，兔子们都很守规矩，按照编号1到m依次排好领取萝卜，萝卜按照编号从小到大的顺序依次发放（也就是编号小的兔子领取前面的萝卜，编号大的兔子领取后面的萝卜，萝卜一定要分完，不能有剩余），每只兔子都只能领取连续的若干袋萝卜，每只兔子至少领取一袋萝卜，一袋萝卜也只能分给一只兔子，不能分给两只以上的兔子。
编程兔希望萝卜尽量能分的平均一点（否则小兔子们要不开心的^_^），也就是它希望得到萝卜最多数量的兔子的萝卜要最少。这个问题对于编程兔来说很简单,亲爱的同学们，你们会么？
输入
第一行是两个正整数n和m，表示萝卜的袋数和兔子的数量。
第二行是n个正整数，表示每袋萝卜的数量。
输出
样例输入 复制
9 3
1 2 3 4 5 6 7 8 9
样例输出 复制
17
提示
输入样例1：
9 3
1 2 3 4 5 6 7 8 9
输出样例1：
17
输入样例2：
5 2
3 2 5 4 3
输出样例2：
10
样例说明：
样例1中，第1-5袋萝卜分给第一只兔子，总数是15个萝卜，第6-7袋萝卜分给第二只兔子，总数是13个萝卜，第8-9袋萝卜分给第三只兔子，总数是17个萝卜，萝卜最多的兔子得了17个萝卜，这是最多的兔子得到的最少的情况。如果第1-4袋分给第一只兔子，共计10个萝卜，第5-7袋分给第二只兔子共计18个萝卜，第8-9袋分给第三只兔子，共计17个萝卜，这样最多的兔子得到了18个萝卜，比之前的方案大，所以不是最优。
样例2中，第1-3袋萝卜分给第一只兔子，得到10个萝卜，第4-5袋萝卜分给第二只兔子，得到7个萝卜，所以最多的兔子得到了10个萝卜，这是最优的情况。
数据规模：
对于60%的数据，1<=m<=n<=100,每袋萝卜的数量不超过10。
对于100%的数据，1<=m<=n<=100000,每袋萝卜的数量不超过10000。