题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$ 和一个整数 $k$，请选取恰好 $k$ 段互不重叠的非空连续子段，使所选元素之和最大。

子段之间可以相邻，但不能包含同一个位置。形式化地，选取 $k$ 个区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k]$，满足：

求这些区间中所有元素的和的最大值。序列是线性的，首尾不相接。

输入格式

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

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示恰好选择 $k$ 段时的最大总和。不需要输出所选区间。

样例 1

5 2
2 -5 4 3 -1

9

样例 1 说明

选择区间 $[1,1]$ 和 $[3,4]$，对应 2 和 4 3，总和为 $9$。

样例 2

4 3
-5 -1 -3 -2

-6

样例 2 说明

选择区间 $[2,2]$、$[3,3]$ 和 $[4,4]$，总和为 $-1-3-2=-6$。必须选满 $3$ 段，不能只选择 $-1$。

样例 3

3 3
1 2 3

6

样例 3 说明

三个子段可以分别为 $[1,1]$、$[2,2]$ 和 $[3,3]$。相邻的子段允许分别计为一段。

数据范围与评分

对于所有数据，$1\le k\le n\le200000$，$n\times k\le2\times10^7$，$-10^9\le a_i\le10^9$。

各组独立计分，只有通过一组内的所有测试点，才能获得该组分数。

答案可能超出 32 位整数的范围，请使用 64 位整数类型（如 C++ 的 long long）。