题目描述

张琪曼进一步研究$\red{k}$个最大连续子序列和问题,即在一个长度为$\red{N}$的数列中,求$\red{k}$个 连续子序列,使得这$\red{k}$个连续子序列的和最大,且$\red{k}$个子序列无公共元素。 即给定由$\red{n}$个整数组成的序列$\red{a_1,a_2,...,a_n(-100≤}$$\red{a_i≤}$$\red{100),}$以及一 个正整数$\red{k,}$要求确定序列$\red{a_1,a_2,...,a_n}$的$\red{k}$个不相交的子段,使这$\red{k}$个子段的总和达到 最大。

输入格式

第一行: $\red{n,k(1≤}$$\red{n≤}$$\red{1 000,2≤}$$\red{k≤}$$\red{10)}$ 第二行: $\red{a_1,a_2,... ,a_n}$每个数中间以空格分隔。

输出格式

$\red{k}$个子段的最大和。

样例

输入样例

10 2
-1 1 -2 3 4 -2 -5 5 6 7

输出样例

25