题目描述

Gug 正在为他的朋友们准备一场盛宴。盛宴由 $N$ 盘食物组成，按顺序排列，第 $i$ 盘食物若被食用，可带来 $A_i$ 点满足感。部分食物可能已经腐烂，因此 $A_i$ 可能为负数。

共有 $K$ 个人参加盛宴，每人将被分配一段连续的食物区间食用。该区间可以为空，且不同人的区间不得重叠，每盘食物最多只能被食用一次。

Gug 希望合理分配食物，使得所有被食用的食物带来的满足感总和最大。

请你计算，最大满足感总和是多少。

输入格式

第一行包含两个整数 $N$ 和 $K$。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出格式

输出一个整数，表示最大满足感总和。

6 1
1 -2 3 -1 5 -6

7

6 2
1 2 3 -10 5 6

17

6 4
-1 -2 -1 0 -5 -1

0

提示

【样例解释】

对于样例 1：

将唯一一人分配到区间 $[3,-1,5]$，满足感总和为 $7$。

对于样例 2：

选择连续区间 $[1,2,3]$ 和 $[5,6]$，总和最大。

对于样例 3：

所有满足感均不为正，最优选择是所有人都选择空区间，总和为 $0$。

【数据范围】

• $1 \leq K \leq N \leq 3 \times 10^5$
• $0 \leq |A_i| \leq 10^9$