A - バッテリー残量と充電器の到着 解説 /

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

配点 : 200 点

問題文

高橋君は N 台のスマートフォンを管理しています。i 番目のスマートフォンの現在のバッテリー残量は W_i パーセントです。

スマートフォンのバッテリーは、充電しなければ 1 日経過するごとに D パーセントポイントずつ減少します。

高橋君は充電器の通販サイトで注文を検討しています。注文すると、ちょうど K 日後に充電器が届きます。現在、高橋君の手元には充電器がないため、届くまでの K 日間は一切充電ができません。

K 日後、充電器が届いた時点での i 番目のスマートフォンのバッテリー残量を W_i - D \times K パーセントとみなします。この値が 1 以上であるスマートフォンは使える状態で残っており、そうでないスマートフォンは電源が切れて使えなくなっているものとします。

N 台のスマートフォンのうち、K 日後に使える状態で残っているものの台数を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq D \leq 100
  • 1 \leq K \leq 10^9
  • 1 \leq W_i \leq 100 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N D K
W_1 W_2 \ldots W_N
  • 1 行目には、スマートフォンの台数を表す整数 N 、1 日あたりのバッテリー減少量を表す整数 D 、充電器が届くまでの日数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各スマートフォンの現在のバッテリー残量を表す整数 W_1, W_2, \ldots, W_N が、スペース区切りで与えられる。

出力

K 日後に使える状態で残っているスマートフォンの台数を 1 行で出力してください。

入力例 1

3 10 5
100 50 30

出力例 1

1

入力例 2

5 15 3
80 45 46 20 100

出力例 2

3

入力例 3

10 7 10
100 70 71 50 35 28 1 72 99 65

出力例 3

4

Score : 200 pts

Problem Statement

Takahashi manages N smartphones. The current battery level of the i-th smartphone is W_i percent.

The battery of a smartphone decreases by D percentage points per day if not charged.

Takahashi is considering ordering from an online charger store. If he places an order, the charger will arrive in exactly K days. Since Takahashi currently has no charger, he cannot charge any smartphone during the K days until it arrives.

After K days, when the charger arrives, the battery level of the i-th smartphone is considered to be W_i - D \times K percent. A smartphone with this value being 1 or more is still usable, while a smartphone with this value less than 1 has powered off and become unusable.

Determine the number of smartphones among the N that are still usable after K days.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq D \leq 100
  • 1 \leq K \leq 10^9
  • 1 \leq W_i \leq 100 (1 \leq i \leq N)
  • All inputs are integers

Input

N D K
W_1 W_2 \ldots W_N
  • The first line contains the integer N representing the number of smartphones, the integer D representing the daily battery decrease, and the integer K representing the number of days until the charger arrives, separated by spaces.
  • The second line contains the integers W_1, W_2, \ldots, W_N representing the current battery levels of each smartphone, separated by spaces.

Output

Output in one line the number of smartphones that are still usable after K days.

Sample Input 1

3 10 5
100 50 30

Sample Output 1

1

Sample Input 2

5 15 3
80 45 46 20 100

Sample Output 2

3

Sample Input 3

10 7 10
100 70 71 50 35 28 1 72 99 65

Sample Output 3

4