大样例下载

问题描述

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

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

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

样例输入

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

接下来：$N$ 个整数 $A_i$

输出

一个整数，表示答案

输入样例

6 2
-1
2
-3
4
-5
6

输出样例

11

数据范围

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