B - Adventurer's Staircase Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君はダンジョンの攻略に挑戦しています。

このダンジョンは N 階層からなり、各階層には 1 から N までの番号が下から順に付けられています。高橋君は最初、階層 1（最下層）にいます。目標は階層 N（最上層）に到達することです。

各階層 i（1 \leq i \leq N - 1）にはモンスターが 1 体ずつ待ち構えており、そのモンスターの強さは E_i です。階層 N にはモンスターはいません。

高橋君は階層 1 から順に 1 階層ずつ上へ進みます。階層を飛ばしたり、引き返したりすることはできません。高橋君が階層 i（1 \leq i \leq N - 1）にいるとき、その階層のモンスターと戦い、勝利しなければ次の階層 i + 1 に進むことはできません。

高橋君の戦闘力は戦闘を通じて変化します。階層 i のモンスターと戦う時点での高橋君の戦闘力を P とすると：

  • P \geq E_i ならば、高橋君はモンスターを倒すことに成功し、階層 i + 1 に進みます。このとき、倒したモンスターの力を吸収し、戦闘力が P + E_i になります。
  • P < E_i ならば、高橋君はモンスターに敗北し、それ以上先に進むことはできません。

高橋君はダンジョンに入る前に「強化薬」を使用することができます。強化薬を 1 個使用すると、戦闘力が 1 増加します。使用する強化薬の個数は 0 個以上 K 個以下の範囲で自由に選べます。強化薬の使用はダンジョンに入る前にのみ行え、冒険中に使用することはできません。

強化薬を使用する前の高橋君の戦闘力は S です。強化薬を j 個（0 \leq j \leq K）使用した場合、冒険開始時（階層 1 のモンスターと戦う前）の戦闘力は S + j となります。

高橋君が階層 N に到達できるような強化薬の使用個数の最小値を求めてください。K 個の強化薬をすべて使用しても階層 N に到達できない場合は -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}
  • 1 行目には、ダンジョンの階層数を表す整数 N、高橋君の強化薬使用前の初期戦闘力を表す整数 S、強化薬の最大使用個数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各階層のモンスターの強さを表す N - 1 個の整数 E_1, E_2, \ldots, E_{N-1} が、スペース区切りで与えられる。

出力

高橋君が階層 N に到達するために必要な強化薬の最小使用個数を 1 行で出力せよ。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

Score : 300 pts

Problem Statement

Takahashi is attempting to conquer a dungeon.

This dungeon consists of N floors, each numbered from 1 to N from bottom to top. Takahashi starts on floor 1 (the bottommost floor). His goal is to reach floor N (the topmost floor).

On each floor i (1 \leq i \leq N - 1), a monster is waiting, and its strength is E_i. There is no monster on floor N.

Takahashi proceeds upward one floor at a time starting from floor 1. He cannot skip floors or go back. When Takahashi is on floor i (1 \leq i \leq N - 1), he must fight and defeat the monster on that floor before he can advance to the next floor i + 1.

Takahashi's combat power changes through battles. Let P be Takahashi's combat power at the time he fights the monster on floor i:

  • If P \geq E_i, Takahashi successfully defeats the monster and advances to floor i + 1. At this time, he absorbs the defeated monster's power, and his combat power becomes P + E_i.
  • If P < E_i, Takahashi is defeated by the monster and cannot proceed any further.

Before entering the dungeon, Takahashi can use "enhancement potions." Using one enhancement potion increases his combat power by 1. He can freely choose to use any number of potions from 0 to K inclusive. Enhancement potions can only be used before entering the dungeon and cannot be used during the adventure.

Takahashi's combat power before using any enhancement potions is S. If he uses j potions (0 \leq j \leq K), his combat power at the start of the adventure (before fighting the monster on floor 1) becomes S + j.

Find the minimum number of enhancement potions Takahashi needs to use in order to reach floor N. If he cannot reach floor N even after using all K enhancement potions, output -1.

Constraints

  • 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)
  • All input values are integers.

Input

N S K
E_1 E_2 \ldots E_{N-1}
  • The first line contains three space-separated integers: N, the number of floors in the dungeon; S, Takahashi's initial combat power before using enhancement potions; and K, the maximum number of enhancement potions he can use.
  • The second line contains N - 1 space-separated integers E_1, E_2, \ldots, E_{N-1}, representing the strength of the monster on each floor.

Output

Output in a single line the minimum number of enhancement potions Takahashi needs to use in order to reach floor N. If he cannot reach floor N even after using all K enhancement potions, output -1.

Sample Input 1

5 2 5
2 5 1 8

Sample Output 1

1

Sample Input 2

4 1 3
10 1 1

Sample Output 2

-1

Sample Input 3

8 1 1000000000000000000
3 8 12 5 20 50 100

Sample Output 3

4