题目内容

你为一款动作游戏设计战士角色的技能：战士每个技能会消耗不同能量，释放技能有 $2$ 个约束：连续释放技能数量不能超过 $m$ 个，技能能量总和不能超过能量上限 $k$；如果超过则必须中断当前技能，进入调息状态（即分段）。

战士有一项爆发技巧：在单次战斗中有一次能量上限翻倍至 $2k$ 的机会，此项场景下战士需使用连续的 $w$ 个技能（技能数量限制 $m$ 依然生效）。

任务目标：

作为战术分析师，你需要为战士规划最优的技能释放序列。给定一套技能的能量消耗列表 $a$，请计算在合理使用爆发机会（或选择不使用）的前提下，释放完所有技能所需的最少分段数（即最少调息次数）。

若存在某个技能的能耗过高，即使开启爆发也无法释放（大于 $2k$），则判定为无解，返回 $-1$。

输入描述

输入参数说明：

• $k$: 能量上限，正整数
• $m$: 单次调息最大技能数，正整数
• $w$: 爆发持续技能数，正整数
• $a$: 技能能量消耗列表，长度为 $n$，每个元素为正整数

数据范围：

• $n$ 为技能数量，即 $a$ 的长度
• $1 \leq w \leq n$
• $1 \leq n \leq 100000$
• $1 \leq m \leq n$
• $1 \leq k \leq 1000000000$
• $1 \leq a[i] \leq 1000000000$

输出描述

输出满足条件的最少分段数（最少调息次数）。若无解则输出 $-1$。

样例1

输入

5,3,2,[3,4,3,4]

输出

3

说明

爆发窗口覆盖索引 $0\sim1$ [3,4] 为 $1$ 段，剩余 [3],[4] 各 $1$ 段 $\rightarrow$ 共 $3$ 段。

样例2

输入

5,3,2,[6, 1, 2, 3]

输出

2

说明

$|a[0]|=6 > k=5$ 且 $|a[0]| < 2k=10$，必须靠爆发窗口覆盖 $a[0]$ 才有解。

样例3

输入

10,5,3,[1, 1, 1, 1, 1]

输出

1

说明

$\text{sum}(a)=5 \leq k=10$ 且 $n=5 \leq m=5$，无需爆发即可 $1$ 段放完。若开启爆发，窗口最多覆盖 $w=3$ 个技能，剩余 $1$ 个技能需另开 $1$ 段，反而变成 $2$ 段，因此不使用爆发更优。