Description

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

Format

Input

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

Output

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

Samples

3 2
-1 -1 -2

-2

Limitation

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