C - Battery Level and Power Saving Mode Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君はノートパソコンを使って N 個のタスクを順番に処理します。タスクは 1 番目から N 番目まで順に実行する必要があります。

i 番目のタスクを完了するには、少なくとも H_i の処理能力が必要です。

高橋君のノートパソコンは初期バッテリー残量 M を持っています。各タスクに対して、以下の 2 種類のモードのうちいずれか一方を選んで実行します。

  • 省エネモード：タスクに対して A の処理能力を発揮する。バッテリー残量は変化しない。
  • フルパワーモード：現在のバッテリー残量を p とするとき、タスクに対して p の処理能力を発揮する。ただし、フルパワーモードを使用するとバッテリーが大きく消耗し、使用後のバッテリー残量は \lfloor p / 2 \rfloor になる（\lfloor x \rfloor は x の小数点以下を切り捨てた値）。

各タスクに対してモードの選択はちょうど 1 回行います。発揮した処理能力がそのタスクの必要処理能力以上であれば、そのタスクを完了できます。

高橋君が N 個すべてのタスクを完了できるかどうか判定してください。完了できる場合、フルパワーモードを使う回数の最小値を求めてください。

制約

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq M \leq 10^{18}
  • 1 \leq A \leq 10^{18}
  • 1 \leq H_i \leq 10^{18}
  • 入力はすべて整数

入力

N M A
H_1 H_2 \ldots H_N
  • 1 行目には、タスクの数 N、初期バッテリー残量 M、省エネモードの処理能力 A が、スペース区切りで与えられる。
  • 2 行目には、各タスクの必要処理能力 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。

出力

すべてのタスクを完了することが可能な場合、フルパワーモードを使う回数の最小値を 1 行で出力してください。

すべてのタスクを完了することが不可能な場合、-1 を 1 行で出力してください。

入力例 1

5 20 5
3 10 4 8 5

出力例 1

2

入力例 2

4 10 3
2 9 6 4

出力例 2

-1

入力例 3

15 1000 50
10 60 45 500 50 200 30 90 49 60 20 50 1 40 45

出力例 3

5

入力例 4

50 1000000000000 1000
500 1000000000000 999 400000000000 1000 200000000000 700 100000000000 1000 60000000000 800 30000000000 200 15000000000 900 7000000000 999 3000000000 123 1500000000 1000 900000000 50 400000000 888 200000000 777 100000000 666 50000000 555 25000000 444 12000000 333 6000000 222 3000000 111 1500000 1000 700000 950 350000 900 200000 800 100000 700 50000

出力例 4

25

入力例 5

1 1000000000000000000 1
1000000000000000000

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi processes N tasks in order using his laptop. The tasks must be executed sequentially from the 1-st task to the N-th task.

To complete the i-th task, a processing power of at least H_i is required.

Takahashi's laptop has an initial battery level of M. For each task, he chooses and executes it in one of the following two modes:

  • Power Saving Mode: Exerts a processing power of A for the task. The battery level does not change.
  • Full Power Mode: Let p be the current battery level. Exerts a processing power of p for the task. However, using Full Power Mode consumes a large amount of battery, and the battery level after use becomes \lfloor p / 2 \rfloor (where \lfloor x \rfloor denotes the greatest integer less than or equal to x).

For each task, the mode selection is made exactly once. If the exerted processing power is greater than or equal to the required processing power for that task, the task can be completed.

Determine whether Takahashi can complete all N tasks. If he can, find the minimum number of times he needs to use Full Power Mode.

Constraints

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq M \leq 10^{18}
  • 1 \leq A \leq 10^{18}
  • 1 \leq H_i \leq 10^{18}
  • All input values are integers.

Input

N M A
H_1 H_2 \ldots H_N
  • The first line contains the number of tasks N, the initial battery level M, and the processing power of the Power Saving Mode A, separated by spaces.
  • The second line contains the required processing power for each task, H_1, H_2, \ldots, H_N, separated by spaces.

Output

If it is possible to complete all tasks, print the minimum number of times Full Power Mode is used in a single line.

If it is impossible to complete all tasks, print -1 in a single line.

Sample Input 1

5 20 5
3 10 4 8 5

Sample Output 1

2

Sample Input 2

4 10 3
2 9 6 4

Sample Output 2

-1

Sample Input 3

15 1000 50
10 60 45 500 50 200 30 90 49 60 20 50 1 40 45

Sample Output 3

5

Sample Input 4

50 1000000000000 1000
500 1000000000000 999 400000000000 1000 200000000000 700 100000000000 1000 60000000000 800 30000000000 200 15000000000 900 7000000000 999 3000000000 123 1500000000 1000 900000000 50 400000000 888 200000000 777 100000000 666 50000000 555 25000000 444 12000000 333 6000000 222 3000000 111 1500000 1000 700000 950 350000 900 200000 800 100000 700 50000

Sample Output 4

25

Sample Input 5

1 1000000000000000000 1
1000000000000000000

Sample Output 5

1