abs loves sequence

题目描述:

abs对于序列有着一定的喜爱

所以他出了这道题来检验你对序列的喜爱程度

abs有一个序列a1,a2,...,an

你可以选择里面最多m个不相交的连续子段

abs想要知道你选择的数的和最大是多少，但他发现自己太菜了，所以来求助于强大的你来帮他解决这个问题。

输入格式:

第一行2个数 n,m

1<=n<=1e5

0<=m<=1e5

第 2 行到第 1+n 行每行一个数 a_i

|a_i|<= 1e4

输出格式:

一行一个数为答案

样例输入:

5 2 
2 -3 2 -1 2

样例输出:

5

时间限制: 1000ms
空间限制: 512MB

---

来源: abs