题目描述

给定一个序列$A$，你可以从中任意选出至多$m$段不相交的闭区间，并使得选出的这$m$段不相交的区间的和最大。

输入格式

输入共两行： 输入第一行：若干个整数，其中第$i$个数字表示序列的第$i$项的值 输入第二行：一个正整数$m$

输出格式

输出共一行，一个正整数，表示选出不相交区间和的最大值

7 -3 6 -10 8
2

18

样例解释 1

选择[1,3]与[5,5]区间，和为7+(-3)+6+8=18

-1 -1 1 -1 -1
3

1

样例解释 2

可以不用选满3组，只选1组，区间为[3,3]，此时的区间和最大值为1

数据范围

设给定序列长度为$n$时，

• 对于 $30\%$ 的数据，$1\leq m \leq n \leq 10^3$；
• 对于 $50\%$ 的数据，$1\leq m \leq n\leq 10^4$；
• 对于另外 $20\%$ 的数据，$1\leq n\leq 5\times10^5$且$1 \leq m \leq 10^2$；
• 对于 $100\%$ 的数据，$1\leq m,n\leq 5\times10^5$
• $-10^9\leq a_i \leq 10^9$；