花环(garland)

题目描述

Kiana有一个漂亮的花环，花环上有\(n\)朵五颜六色的花儿，这些花儿构成了一个环形的结构，沿顺时针方向依次编号为\(1,2,\cdots,n\)，且第\(n\)朵花儿与第\(1\)朵花儿也是相邻的。

Kiana的小伙伴们都喜欢花儿，于是Kiana决定献出自己的花环，把花儿分给自己的朋友。具体而言，Kiana共有\(m\)个小伙伴，故她希望在花环上剪下\(m\)段连续的区间来，每个区间可以包含任意多朵花儿，但每朵花儿至多属于一个区间。

当然，并非每朵花儿都讨Kiana喜爱，于是她给了每朵花儿一个魅力值，其中有些好看的花儿魅力值就为正数，有些Kiana觉得不好看的花儿魅力值就为负数。

Kiana希望自己剪下来送给小伙伴的花儿的魅力值总和尽可能大，并想求出这个最大值是多少。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式

第一行包含两个正整数\(n\)和\(m\)，分别表示花环上花儿的数量与Kiana的小伙伴数量。

第二行包含\(n\)个整数，其中第\(i\)个整数\(F_i\)表示第\(i\)朵花儿的魅力值。数据保证至少有\(m\)朵花儿的魅力值是正数，即Kiana最后得到的魅力值总和总是可以大于\(0\)的。

输出格式

输出一行一个正整数，表示Kiana能够剪下来的花儿的最大魅力值总和。

输入输出样例

输入样例#1：

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

输出样例#1：

37

输入样例#2：

garland2.in

输出样例#2：

garland2.ans

输入样例#3：

garland3.in

输出样例#3：

garland3.ans

输入样例#4：

garland4.in

输出样例#4：

garland4.ans

输入样例#5：

garland5.in

输出样例#5：

garland5.ans

样例解释

Kiana的花环上共有\(10\)朵花儿，其魅力值依次为\(-1,6,-2,7,-3,8,-4,9,-5,10\)，Kiana需要从中选出\(3\)个区间来送给自己的小伙伴。那么，Kiana会选择第\(10,1,2,3,4\)朵花构成的区间和第\(6\)朵、第\(8\)朵花单独构成的两个区间，第\(1\)个区间的魅力值为\(10+(-1)+6+(-2)+7=20\)，后两个区间的魅力值分别为\(8\)和\(9\)，故总的魅力值为\(20+8+9=37\)，可以证明这是魅力值最大的选择方案。

数据范围

对于\(25\%\)的数据，保证\(1\leq n\leq 30,1\leq m\leq 10\)。

对于\(50\%\)的数据，保证\(1\leq n\leq 3000,1\leq m\leq 1000\)。

对于\(100\%\)的数据，保证\(1\leq n\leq 3\times 10^5,1\leq m\leq 10^5,-100\leq F_i\leq 100\)且\(F_i\neq 0\)。

上面每一档数据内部，各有\(20\%\)的数据保证\(m=1\)，还有\(20\%\)的数据保证\(m=2\)，另有\(20\%\)的数据保证\(m\leq 10\)。