大样例下载

问题描述

N 个整数 $A_1, A_2, ……, A_N$ 排成一排，可能有的整数为负数。

现在让你从中取出 M 个子段，要求任意两个子段不能有重叠部分，每个子段包含的元素在原序列中必须是连续的。特别地，不包含任何元素的空子段也是可以的。

你希望取出的这 M 个子段包含的所有元素的和是最大的。请你输出这个最大值。

样例输入

第一行：包含两个整数 N, M

接下来 ：N个整数 $A_i$

输出

一个整数，表示答案

输入样例

6 2
-1
3
-2
4
-5
6

输出样例

11

数据范围

$2 ≤ M ≤ N ≤ 10^5, M ≤ 100, |A_i| ≤ 10^9$