分糖果

小 W 有 $N$ 颗糖果，希望将它们分给 $k$ 个小朋友。每颗糖果都有一个美味值，美味值可能为负数。

小 W 要求每个小朋友分到编号连续的一段糖果，且每个小朋友至少分到一颗糖果。所有糖果都必须恰好分完，因此需要将糖果序列划分为 $k$ 个非空的连续子段。

每个小朋友分到的糖果的美味值之和，称为该小朋友获得的总美味值。小 W 希望所有小朋友中最大的总美味值尽可能小。请你求出这个最小值。

输入格式

第一行包含两个整数 $N$ 和 $k$，分别表示糖果数量和小朋友数量。

第二行包含 $N$ 个整数，其中第 $i$ 个整数 $a_i$ 表示编号为 $i$ 的糖果的美味值。

输出格式

输出一行一个整数，表示所有划分方案中，最大总美味值的最小值。

样例输入

3 2
    -1 -1 -2

样例输出

-2

数据范围

• $1\le k\le N\le 2\times 10^4$；
• $-32768\le a_i\le 32767$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3 2
    -1 -1 -2

输出

-2