A - Sanitize Hands Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

消毒液の入ったボトルがあり、その消毒液によってちょうど M 本の手を消毒することができます。

N 人の宇宙人が順に手の消毒を行いに来ます。
i 人目 (1\leq i\leq N) の宇宙人は H_i 本の手を持っており、それぞれ自身のすべての手を 1 回ずつ消毒したいと考えています。

何人目の宇宙人までがすべての手を消毒できるか求めてください。
ただし、ある宇宙人が消毒を始める時点で、自身のすべての手を消毒する分の消毒液が残っていなかったとしても、その宇宙人はその消毒液を使い切ってしまうものとします。

制約

  • 1\leq N,M\leq 100
  • 1\leq H_i\leq 100
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
H_1 H_2 \ldots H_N

出力

何人目の宇宙人までが自身のすべての手を消毒できるか出力せよ。

入力例 1

5 10
2 3 2 5 3

出力例 1

3

次の手順で宇宙人は自身の手を消毒します。

  • 1 人目の宇宙人は自身の 2 本の手を消毒します。残りの消毒液によって、10-2=8 本の手を消毒できます。
  • 2 人目の宇宙人は自身の 3 本の手を消毒します。残りの消毒液によって、8-3=5 本の手を消毒できます。
  • 3 人目の宇宙人は自身の 2 本の手を消毒します。残りの消毒液によって、5-2=3 本の手を消毒できます。
  • 4 人目の宇宙人は 5 本の手を持っていますが、消毒液は 3 本分しかないため消毒液を使い切り、かつ自身のすべての手を消毒できません。

よって、3 人目の宇宙人までが自身のすべての手を消毒できるため、3 を出力します。

入力例 2

5 10
2 3 2 3 5

出力例 2

4

入力例 3

1 5
1

出力例 3

1

すべての宇宙人が自身の手を消毒することができます。

Score : 100 points

Problem Statement

There is a bottle of disinfectant that can disinfect exactly M hands.

N aliens come one by one to disinfect their hands.
The i-th alien (1 \leq i \leq N) has H_i hands and wants to disinfect all of their hands once.

Determine how many aliens can disinfect all of their hands.
Here, even if there is not enough disinfectant left for an alien to disinfect all of their hands when they start, they will use up the remaining disinfectant.

Constraints

  • 1 \leq N, M \leq 100
  • 1 \leq H_i \leq 100
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
H_1 H_2 \ldots H_N

Output

Print the number of aliens who can disinfect all of their hands.

Sample Input 1

5 10
2 3 2 5 3

Sample Output 1

3

The aliens disinfect their hands in the following steps:

  • The first alien disinfects their two hands. The remaining disinfectant can disinfect 10-2=8 hands.
  • The second alien disinfects their three hands. The remaining disinfectant can disinfect 8-3=5 hands.
  • The third alien disinfects their two hands. The remaining disinfectant can disinfect 5-2=3 hands.
  • The fourth alien has five hands, but there is only enough disinfectant for three hands, so they use up the disinfectant without disinfecting all of their hands.

Thus, the first three aliens can disinfect all of their hands, so print 3.

Sample Input 2

5 10
2 3 2 3 5

Sample Output 2

4

Sample Input 3

1 5
1

Sample Output 3

1

All aliens can disinfect their hands.