分数: 300 分
问题陈述
高桥正在尝试征服地牢。
这个地牢包括 N 楼层,每层编号从 1 to N 从下到上。高桥开始在地板上 1 (最底层)。他的目标是到达地板 N (最顶层)。
每层楼 i (1 \leq i \leq N - 1),有怪物正在等待,其力量为 E_i。地板上没有怪物 N.
高桥从一层开始,一次向上一层 1。他不能跳过楼层或回去。当高桥在地板上时 i (1 \leq i \leq N - 1),他必须战斗并击败该层的怪物才能进入下一层 i + 1.
高桥的战斗力通过战斗而变化。让 P 是高桥与地板上的怪物战斗时的战斗力 i:
- If P \geq E_i,高桥成功击败怪物并晋级楼层 i + 1。此时他吸收了被击败的怪物的力量,战斗力变得 P + E_i.
- If P < E_i,高桥被怪物击败,无法继续前进。
进入地下城之前,高桥可以使用“强化药剂”。使用一种增强药剂可以增加他的战斗力 1。他可以自由选择使用任意数量的药剂 0 to K 包括在内。强化药剂只能在进入地下城之前使用,冒险过程中不能使用。
高桥在使用任何强化药剂之前的战斗力为 S。如果他使用 j 药水(0 \leq j \leq K),冒险开始时的战斗力(在与地板上的怪物战斗之前) 1) 变为 S + j.
找出高桥到达楼层所需使用的最少增强药水数量 N。如果他无法到达地板 N 即使使用完所有 K 强化药水,输出 -1.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq S \leq 10^9
- 0 \leq K \leq 10^{18}
- 1 \leq E_i \leq 10^9 (1 \leq i \leq N - 1)
- 所有输入值均为整数。
输入
N S K
E_1 E_2 \ldots E_{N-1}
- 第一行包含三个空格分隔的整数: N,地牢的层数; S,高桥使用强化药剂前的初始战斗力;和 K,他可以使用的增强药水的最大数量。
- 第二行包含 N - 1 空格分隔的整数 E_1, E_2, \ldots, E_{N-1},代表每层怪物的强度。
输出
在一行中输出高桥到达楼层所需使用的最小增强药水数量 N。如果他无法到达地板 N 即使使用完所有 K 强化药水,输出 -1.
示例输入 1
5 2 5 2 5 1 8
示例输出 1
1
示例输入 2
4 1 3 10 1 1
示例输出 2
-1
示例输入 3
8 1 1000000000000000000 3 8 12 5 20 50 100
示例输出 3
4