B - スマートフォンのバッテリー 解説 /

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

配点 : 300 点

問題文

高橋君は旅行の計画を立てています。

高橋君は N 台のスマートフォンを持っています。各スマートフォンには 1 から N までの番号が付けられており、スマートフォン i の現在のバッテリー残量は A_i %です。バッテリー残量は整数値で管理され、0 %未満になることはありません。

バッテリー残量が L %以下のスマートフォンは電源が切れた状態であり、使用できません。したがって、現在の時点で A_i \leq L であるスマートフォン i は最初から電源が切れています。一度電源が切れたスマートフォンは、以降再び使用可能になることはありません。

高橋君はモバイルバッテリーを 1 台持っています。現在の時刻を時刻 0 とします。時刻 0 において、高橋君はその時点で電源が入っているスマートフォンの中から K 台以下（0 台でもよい）を選んでモバイルバッテリーに接続できます。モバイルバッテリーに接続されたスマートフォンは、時刻 Y の処理がすべて終わるまで接続が維持され、その間バッテリー残量は一切減少しません。途中で接続を外したり、別のスマートフォンに付け替えたりすることはできません。また、電源が切れているスマートフォンをモバイルバッテリーに接続することはできません。

モバイルバッテリーへの接続が完了した後、時刻 1, 時刻 2, \ldots, 時刻 Y のそれぞれにおいて、以下の処理がこの順で行われます。

  1. バッテリー消費： 電源が入っているスマートフォンのうち、モバイルバッテリーに接続されていないもののバッテリー残量がそれぞれ 1 %減少します。
  2. 電源切れ判定： モバイルバッテリーに接続されていないスマートフォンについて、バッテリー残量が L %以下になったものの電源が切れます。

高橋君がモバイルバッテリーに接続するスマートフォンを最適に選んだとき、時刻 Y の処理がすべて終わった直後の時点で電源が入っている（使用可能な）スマートフォンは最大で何台になるか求めてください。モバイルバッテリーに接続されているスマートフォンも、電源が入っていればこの台数に含みます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq L \leq 99
  • 0 \leq K \leq N
  • 1 \leq Y \leq 100
  • 1 \leq A_i \leq 100
  • 入力はすべて整数

入力

N L K Y
A_1 A_2 \ldots A_N
  • 1 行目には、スマートフォンの台数を表す N 、電源が切れるバッテリー残量の閾値を表す L 、モバイルバッテリーに同時に接続できる最大台数を表す K 、経過時間を表す Y が、スペース区切りで与えられる。
  • 2 行目には、各スマートフォンの現在のバッテリー残量を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

時刻 Y の処理がすべて終わった直後の時点で電源が入っているスマートフォンの最大台数を 1 行で出力してください。

入力例 1

5 10 2 5
50 12 8 30 14

出力例 1

4

入力例 2

8 20 3 10
100 35 25 50 18 30 22 80

出力例 2

7

入力例 3

10 0 1 50
100 48 51 30 75 50 60 10 49 55

出力例 3

6

Score : 300 pts

Problem Statement

Takahashi is planning a trip.

Takahashi has N smartphones. Each smartphone is numbered from 1 to N, and smartphone i currently has a battery level of A_i %. Battery levels are managed as integer values and never go below 0 %.

A smartphone with a battery level of L % or less is powered off and cannot be used. Therefore, smartphone i with A_i \leq L at the current time is already powered off from the start. Once a smartphone is powered off, it can never become usable again.

Takahashi has one mobile battery. Let the current time be time 0. At time 0, Takahashi can choose at most K smartphones (possibly 0) from among the currently powered-on smartphones and connect them to the mobile battery. Smartphones connected to the mobile battery remain connected until all processing at time Y is complete, and their battery levels do not decrease at all during this period. It is not possible to disconnect them midway or switch the connection to a different smartphone. Also, a powered-off smartphone cannot be connected to the mobile battery.

After the mobile battery connections are made, at each of time 1, time 2, \ldots, time Y, the following operations are performed in this order:

  1. Battery consumption: For each powered-on smartphone that is not connected to the mobile battery, its battery level decreases by 1 %.
  2. Power-off check: For smartphones not connected to the mobile battery, any smartphone whose battery level has become L % or less is powered off.

When Takahashi optimally chooses which smartphones to connect to the mobile battery, find the maximum number of smartphones that are powered on (usable) immediately after all processing at time Y is complete. Smartphones connected to the mobile battery are also counted if they are powered on.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq L \leq 99
  • 0 \leq K \leq N
  • 1 \leq Y \leq 100
  • 1 \leq A_i \leq 100
  • All inputs are integers

Input

N L K Y
A_1 A_2 \ldots A_N
  • The first line contains N representing the number of smartphones, L representing the battery level threshold at which a smartphone powers off, K representing the maximum number of smartphones that can be simultaneously connected to the mobile battery, and Y representing the elapsed time, separated by spaces.
  • The second line contains A_1, A_2, \ldots, A_N representing the current battery levels of each smartphone, separated by spaces.

Output

Print on one line the maximum number of smartphones that are powered on immediately after all processing at time Y is complete.

Sample Input 1

5 10 2 5
50 12 8 30 14

Sample Output 1

4

Sample Input 2

8 20 3 10
100 35 25 50 18 30 22 80

Sample Output 2

7

Sample Input 3

10 0 1 50
100 48 51 30 75 50 60 10 49 55

Sample Output 3

6