1054 - 单调队列DP: 子序列之和最大[模板]

通过次数

20

提交次数

62

时间限制 : 1 秒
内存限制 : 512 MB

给你n各数字构成的数字序列,请你找出其中多个连续一段数字,使得这些段数字之和最大,且每段数字数量小于等于k

输入

第一行二个整数表示n各k 接下来n行,表示n每个数字

输出

输出一个整数,表示最大值 保证最大值在long long 内

样例

输入

5 2
1
2
3
4
5

输出

12

提示

1<=n<=2000000

每个数字范围在[0,10^9]之间

样例解释:分成【1 2】,【4 5】 加起来为12