A - Dungeon Exploration Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君はダンジョンを探索しています。

ダンジョンには N 体のモンスターが一列に並んでおり、i 番目のモンスターの強さは H_i です。高橋君は初期体力 P で、1 番目のモンスターから N 番目のモンスターまで順番に 1 体ずつ戦います。モンスターを飛ばしたり、戻って再戦したりすることはできません。

高橋君がモンスター i と戦うとき、現在の体力に応じて以下のいずれか一方が起こります：

  • 現在の体力が H_i 以上であれば、モンスターを倒すことに成功し、体力が H_i だけ 減少 する。
  • 現在の体力が H_i 未満であれば、モンスターを倒すことに失敗する。このとき、モンスターから反撃を受けた衝撃で逆に力が覚醒し、体力が H_i だけ 増加 する。モンスターは倒せないまま、次のモンスターへ進む。

体力に上限はなく、戦闘の結果体力がちょうど 0 になっても探索は続行します。なお、上記のルールにより、体力が負になることはありません。

すべてのモンスターとの戦闘が終わったとき、高橋君が倒すことに成功したモンスターの数を求めてください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq P \leq 10^9
  • 1 \leq H_i \leq 10^9
  • 入力はすべて整数である

入力

N P
H_1 H_2 \ldots H_N
  • 1 行目には、モンスターの数を表す N と、高橋君の初期体力を表す P が、スペース区切りで与えられる。
  • 2 行目には、各モンスターの強さを表す H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。

出力

高橋君が倒すことに成功したモンスターの数を 1 行で出力してください。

入力例 1

5 7
3 10 4 8 2

出力例 1

4

入力例 2

4 2
5 1 10 3

出力例 2

2

入力例 3

12 20
5 7 30 10 12 1 40 8 50 20 3 60

出力例 3

9

入力例 4

20 100
20 50 40 200 30 60 10 500 100 90 80 70 60 50 400 30 20 10 1000 5

出力例 4

15

入力例 5

1 1
1

出力例 5

1

Score : 233 pts

Problem Statement

Takahashi is exploring a dungeon.

In the dungeon, N monsters are lined up in a row, and the strength of the i-th monster is H_i. Takahashi starts with an initial health of P and fights the monsters one by one in order from the 1-st to the N-th. He cannot skip monsters or go back to fight them again.

When Takahashi fights monster i, one of the following occurs depending on his current health:

  • If his current health is greater than or equal to H_i, he successfully defeats the monster, and his health decreases by H_i.
  • If his current health is less than H_i, he fails to defeat the monster. In this case, the shock of the monster's counterattack instead awakens his power, and his health increases by H_i. The monster remains undefeated, and he proceeds to the next monster.

There is no upper limit on health, and even if his health becomes exactly 0 as a result of a battle, the exploration continues. Note that, due to the rules above, his health will never become negative.

After all battles with the monsters are finished, determine the number of monsters that Takahashi successfully defeated.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq P \leq 10^9
  • 1 \leq H_i \leq 10^9
  • All input values are integers.

Input

N P
H_1 H_2 \ldots H_N
  • The first line contains N, the number of monsters, and P, Takahashi's initial health, separated by a space.
  • The second line contains H_1, H_2, \ldots, H_N, the strengths of the monsters, separated by spaces.

Output

Print the number of monsters that Takahashi successfully defeated, in a single line.

Sample Input 1

5 7
3 10 4 8 2

Sample Output 1

4

Sample Input 2

4 2
5 1 10 3

Sample Output 2

2

Sample Input 3

12 20
5 7 30 10 12 1 40 8 50 20 3 60

Sample Output 3

9

Sample Input 4

20 100
20 50 40 200 30 60 10 500 100 90 80 70 60 50 400 30 20 10 1000 5

Sample Output 4

15

Sample Input 5

1 1
1

Sample Output 5

1