← 返回题目列表

AtCoder · awc0096_b

B. 冒险家的楼梯

中文机器翻译题面 查看原题

分数: 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