题目内容

在一个远古修士的洞穴中，探宝者发现了一排共 N 棵灵草，每棵灵草有一个灵力值 A，灵力值可为正、负或零。

为避免灵草被探宝者一扫而空，远古修士设置了禁制，要求探宝者必须选择一段连续的灵草序列带回，且必须满足以下规则：

规则一：选中的连续序列中，灵力值为正的数量不少于 K 棵。

规则二：在满足规则一的前提下，探宝者还可以从选中序列中额外挑选最多 M 棵灵力值为负的灵草丢弃，以提升总收益。

求所有合法选择方案中，能够走灵草的灵力值总和的最大值。如果无法满足规则一，输出 -1。

数据范围：

• 1 <= N <= 10^4
• 1 <= K <= N
• 0 <= M <= 5
• -10^9 <= A <= 10^9

输入描述

输入格式：

N,K,M,[a1,a2,a3,...,aN]

其中：

• N 表示灵草数量
• K 表示至少需要选择的正数灵草数量
• M 表示最多可丢弃的负数灵草数量
• [a1,a2,...,aN] 表示灵草灵力值数组

输出描述

输出一个整数，表示最大灵力值总和；若不存在满足条件的连续子序列，则输出 -1。

样例1

输入

8,3,2,[3,-5,4,-1,2,-8,6,-2]

输出

14

说明

• 选中序列 [3,-5,4,-1,2,-8,6]（下标 1~7），灵力值为正的灵草有 3、4、2、6 共 4 棵且 >= K=3，满足规则一。
• 该序列总和 = 3 + (-5) + 4 + (-1) + 2 + (-8) + 6 = 1。
• 丢弃最多 M=2 棵负灵力值灵草：选 -8 和 -5 丢弃，剩余总和 = 1 - (-8) - (-5) = 14。

样例2

输入

5,4,1,[-1,-2,3,-4,5]

输出

-1

说明

任意连续子序列中正灵力值灵草最多只有 3 棵（如 [1,-2,3,-4,5] 中正值为 1、3、5），无法达到 K=4。