分糖果

时间限制:10s      空间限制:128MB

题目描述

    小W有N颗糖果,去助学的时候,小W希望将这N颗糖果分给所在的k个小朋友。小W是个很怪的人,他觉得,每个小朋友应该分得编号连续的一段糖果,而且每个小朋友至少应该得到一颗糖果。奇怪的不知这一点,小W给每颗糖果一个值用来表示它的美味度(可以为负数),作为一个绝对公平的追求者,他当然希望将所有糖果公平的分给所有小朋友,所以他希望这些小朋友所得到的最大糖果美味值之和尽量小。
    小W定制了这样一套奇怪的规则,他却不知道该如何分糖果了,这个艰巨的任务就交给了你。


输入格式

    第一行两个整数N,k。
    第二行N个数,第i个整数表示第i号糖果的美味值。
 


输出格式

 
   仅一行一个数,表示最小的最大糖果美味值之和。
 


样例输入

   3 2
    -1 -1 -2
 

样例输出

   -2
 

提示

    对于100%的数据,N<=20000    k<=N


题目来源

没有写明来源

Menuappsclose