A - 連鎖するバケツ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君は N 個のバケツを使って、雨水を集める実験をしています。バケツには 1 から N までの番号が付けられており、バケツ i の容量は C_i リットルです。最初、すべてのバケツは空です。

バケツは一列に連結されており、水は次のように流れます。高橋君はバケツ 1 に合計 W リットルの水を連続的に注ぎます。バケツ i (1 \leq i \leq N-1) に流れ込んだ水は、バケツ i の容量 C_i に達するまではバケツ i に溜まります。バケツ i が満杯（容量 C_i リットルちょうどの水が溜まっている状態）になった後、さらにバケツ i に流れ込む水はすべてバケツ i+1 へと流れ込みます。バケツ N が満杯になった後にさらに流れ込む水は、すべて外に溢れて失われます。

すべての水を注ぎ終えた時点で、満杯になっているバケツの個数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq 10^{18}
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N W
C_1 C_2 \cdots C_N
  • 1 行目には、バケツの個数を表す整数 N と、注がれる水の総量（リットル）を表す整数 W が、スペース区切りで与えられる。
  • 2 行目には、各バケツの容量を表す整数 C_1, C_2, \ldots, C_N が、スペース区切りで与えられる。
  • C_i はバケツ i の容量（リットル）を表す。

出力

満杯になったバケツの個数を 1 行で出力してください。

入力例 1

3 10
3 4 5

出力例 1

2

入力例 2

5 25
5 10 3 8 6

出力例 2

3

入力例 3

6 1000000000000000000
100000000 200000000 300000000 400000000 500000000 600000000

出力例 3

6

Score : 266 pts

Problem Statement

Takahashi is conducting an experiment to collect rainwater using N buckets. The buckets are numbered from 1 to N, and bucket i has a capacity of C_i liters. Initially, all buckets are empty.

The buckets are connected in a single line, and water flows as follows. Takahashi continuously pours a total of W liters of water into bucket 1. Water that flows into bucket i (1 \leq i \leq N-1) accumulates in bucket i until it reaches bucket i's capacity C_i. After bucket i becomes full (exactly C_i liters of water have accumulated), any additional water that flows into bucket i will all flow into bucket i+1. After bucket N becomes full, any additional water that flows in will all overflow and be lost.

Determine the number of buckets that are full after all the water has been poured.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq 10^{18}
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N W
C_1 C_2 \cdots C_N
  • The first line contains an integer N representing the number of buckets and an integer W representing the total amount of water (in liters) to be poured, separated by a space.
  • The second line contains integers C_1, C_2, \ldots, C_N representing the capacity of each bucket, separated by spaces.
  • C_i represents the capacity (in liters) of bucket i.

Output

Print the number of buckets that are full in a single line.

Sample Input 1

3 10
3 4 5

Sample Output 1

2

Sample Input 2

5 25
5 10 3 8 6

Sample Output 2

3

Sample Input 3

6 1000000000000000000
100000000 200000000 300000000 400000000 500000000 600000000

Sample Output 3

6