8303: 最大子段和 V3
[Creator : ]
Description
环形最大 $M$ 子段和，$N$ 个整数组成的序列排成一个环， a[1],a[2],a[3], …, a[n] （a[n−1],a[n],a[1] 也可以算作 1 段），将这 N 个数划分为互不相交的 M 个子段，并且这 M 个子段的和是最大的。如果 M≥N 个数中正数的个数，那么输出所有正数的和。
例如： -2 11 -4 13 -5 6 -1 ，分为 2 段， 6 -1 -2 11 一段， 13 一段，和为 27。
例如： -2 11 -4 13 -5 6 -1 ，分为 2 段， 6 -1 -2 11 一段， 13 一段，和为 27。
Input
第 1 行： 2 个数 $N,M\ (2 \leq N,M \leq 100,000)$，中间用空格分隔。N 为整数的个数，M 为划分为多少段。
第 2 ~ N+1 行：N 个整数 $a_i\ (-10^9 \leq a_i \leq 10^9)$
第 2 ~ N+1 行：N 个整数 $a_i\ (-10^9 \leq a_i \leq 10^9)$
Output
输出这个最大和
Sample 1 Input
7 2
-2
11
-4
13
-5
6
-2
Sample 1 Output
26