#2862. 分糖果

内存限制:128 MiB 时间限制:10 Sec

题目描述

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

输入格式

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

输出格式

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

样例

样例输入


			

3 2
-1 -1 -2

样例输出


			

-2

数据范围与提示

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