Gug 正在为他的朋友们准备一场盛宴。盛宴包含 $N$ 盘食物，排成一行。从左往右数第 $i$ 盘食物如果被吃掉，会提供 $A_i$ 点满意度。由于有些食物可能已经腐烂，因此 $A_i$ 可能是负数。
盛宴共有 $K$ 个人参加，每个人将被分配一个连续的食物段来食用。这个段可以是空的。两个人的段不能重叠，因为食物不能被吃两次。Gug 希望将这些盘子分配给他的朋友们，使得所有人吃掉的食物的满意度之和最大化。
输入格式
程序必须从标准输入读取数据。 输入的第一行包含两个整数 $N$ 和 $K$。 下一行包含 $N$ 个整数 $A_1, \dots, A_N$。
输出格式
程序必须输出到标准输出。 输出应包含一个整数，即最优分配方案下满意度之和的最大值。
数据范围
对于所有测试用例，输入满足以下限制： $1 \le K \le N \le 3 \times 10^5$ $0 \le |A_i| \le 10^9$
程序将在满足以下限制的输入实例上进行测试：
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 4 | $A_i \ge 0$ |
| 2 | 8 | 最多只有一个位置满足 $A_i < 0$ |
| 3 | 18 | $K = 1$ |
| 4 | 10 | $1 \le K \le N \le 80$ |
| 5 | 11 | $1 \le K \le N \le 300$ |
| 6 | 20 | $1 \le K \le N \le 2000$ |
| 7 | 29 | - |
样例
样例输入 1
6 1 1 -2 3 -1 5 -6
样例输出 1
7
说明 1
将唯一的人分配给段 $[3, -1, 5]$ 是最优的。
样例输入 2
6 2 1 2 3 -10 5 6
样例输出 2
17
说明 2
选择连续段 $[1, 2, 3]$ 和 $[5, 6]$ 是最优解。
样例输入 3
6 4 -1 -2 -1 0 -5 -1
样例输出 3
0
说明 3
由于所有的满意度点数均为非正数，因此为四个人都选择空段是最优的。