花环(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$。