题目描述

小 W 有 $n$ 颗糖果，去助学的时候，小 W 希望将这 $n$ 颗糖果分给所在的 $k$ 个小朋友。

小 W 是个很怪的人，他觉得，每个小朋友应该分得编号连续的一段糖果，而且每个小朋友至少应该得到一颗糖果。

小 W 给每颗糖果一个值 $v_i$ 用来表示它的美味度（可以为负数）。作为一个绝对公平的追求者，他当然希望将所有糖果公平的分给所有小朋友，所以他希望这些小朋友所得到的最大糖果美味值之和尽量小。

小 W 定制了这样一套奇怪的规则，他却不知道该如何分糖果了，这个艰巨的任务就交给了你。

输入格式

第一行两个整数 $n,k$。

接下来一行 $n$ 个整数表示 $v_{1\cdots n}$。

输出格式

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

3 2
-1 -1 -2

-2

数据规模与约定

对于 $100\%$ 的数据，$1\leq k\leq n\leq 2\times 10^4$。