B - 花壇の防衛戦 解説 /

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

配点 : 300 点

問題文

高橋君は N 個の鉢植えを一列に並べて育てています。左から順に 1, 2, \ldots, N と番号が付けられており、鉢植え i には現在 A_i ミリリットルの水が入っています。

夏の暑さにより、毎日すべての鉢植えから水が蒸発します。具体的には、 1 日が経過するごとに各鉢植えの水量が D ミリリットルずつ減少します（ただし、水量が 0 未満になることはなく、 0 で止まります）。

一方、いたずら好きの青木君は、高橋君の花壇を台無しにしようと企んでいます。青木君は毎日の始まりに 1 回だけ行動でき、任意の鉢植えを 1 つ選んでその鉢植えの水量を 0 にすることができます（水を捨てるいたずら）。青木君はこの行動を合計 K 回まで行えます。ただし、同じ鉢植えを複数回選ぶこともできます。青木君のいたずらは、その日の蒸発による減少が起こる前に実行されます。

高橋君は水を補充する手段を持っておらず、蒸発やいたずらを防ぐこともできません。 M 日後（ M 日分の蒸発と青木君のいたずらがすべて終わった後）に、水量が 1 ミリリットル以上残っている鉢植えの数をできるだけ多く保ちたいと考えています。

青木君は高橋君にとって最悪の結果になるように最適に行動します。つまり、青木君は M 日後に水量が 1 以上の鉢植えの数を最小化するようにいたずらの対象を選びます。

青木君が最適に行動したとき、 M 日後に水量が 1 ミリリットル以上残っている鉢植えの数を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 10^9
  • 1 \leq D \leq 10^9
  • 0 \leq K \leq N
  • 0 \leq A_i \leq 10^{18}
  • 入力はすべて整数である

入力

N M D K
A_1 A_2 \ldots A_N
  • 1 行目には、鉢植えの数 N 、経過日数 M 、 1 日あたりの蒸発量 D 、青木君のいたずら回数の上限 K が、スペース区切りで与えられる。
  • 2 行目には、各鉢植えの初期水量 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

青木君が最適にいたずらを行ったとき、 M 日後に水量が 1 ミリリットル以上残っている鉢植えの数を 1 行で出力せよ。

入力例 1

5 3 2 1
1 5 6 7 10

出力例 1

1

入力例 2

4 2 3 0
0 5 6 7

出力例 2

1

入力例 3

12 10 7 3
0 1 69 70 71 100 150 35 80 500 70 72

出力例 3

3

入力例 4

40 123456789 98765 15
0 100 1000000000 5000000000 10000000000 12190000000000 12193209765584 12193209765585 12193209765586 15000000000000 20000000000000 999999999999999999 123456789012345678 42 7777777777777 8888888888888 9999999999999 11111111111111 22222222222222 33333333333333 44444444444444 55555555555555 66666666666666 77777777777777 88888888888888 99999999999999 314159265358979323 271828182845904523 1000000000000000000 999999999999999998 12193209765583 12193209765584 12193209765585 1 2 3 4 5 6 7

出力例 4

2

入力例 5

1 1 1 1
1000000000000000000

出力例 5

0

Score : 300 pts

Problem Statement

Takahashi is growing N potted plants arranged in a row. They are numbered 1, 2, \ldots, N from left to right, and plant i currently contains A_i milliliters of water.

Due to the summer heat, water evaporates from all potted plants every day. Specifically, as each day passes, the amount of water in each plant decreases by D milliliters (however, the amount of water will never drop below 0; it stops at 0).

Meanwhile, the mischievous Aoki is planning to ruin Takahashi's flowerbed. Aoki can perform an action at most once at the beginning of each day: he can choose any single potted plant and set its water amount to 0 (a prank of discarding the water). Aoki can perform this action up to K times in total. He may choose the same potted plant multiple times. Aoki's pranks are executed before the evaporation for that day occurs.

Takahashi has no way to refill the water, nor can he prevent evaporation or Aoki's pranks. He wants to keep the number of potted plants with at least 1 milliliter of water remaining after M days (after all M days of evaporation and Aoki's pranks are completed) as large as possible.

Aoki acts optimally to achieve the worst possible outcome for Takahashi. In other words, Aoki chooses the targets of his pranks to minimize the number of potted plants with at least 1 milliliter of water remaining after M days.

Find the number of potted plants with at least 1 milliliter of water remaining after M days, assuming Aoki acts optimally.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 10^9
  • 1 \leq D \leq 10^9
  • 0 \leq K \leq N
  • 0 \leq A_i \leq 10^{18}
  • All input values are integers.

Input

N M D K
A_1 A_2 \ldots A_N
  • The first line contains the number of potted plants N, the number of days M, the daily evaporation amount D, and the maximum number of Aoki's pranks K, separated by spaces.
  • The second line contains the initial water amounts of the potted plants A_1, A_2, \ldots, A_N, separated by spaces.

Output

Print the number of potted plants with at least 1 milliliter of water remaining after M days, assuming Aoki acts optimally, in a single line.

Sample Input 1

5 3 2 1
1 5 6 7 10

Sample Output 1

1

Sample Input 2

4 2 3 0
0 5 6 7

Sample Output 2

1

Sample Input 3

12 10 7 3
0 1 69 70 71 100 150 35 80 500 70 72

Sample Output 3

3

Sample Input 4

40 123456789 98765 15
0 100 1000000000 5000000000 10000000000 12190000000000 12193209765584 12193209765585 12193209765586 15000000000000 20000000000000 999999999999999999 123456789012345678 42 7777777777777 8888888888888 9999999999999 11111111111111 22222222222222 33333333333333 44444444444444 55555555555555 66666666666666 77777777777777 88888888888888 99999999999999 314159265358979323 271828182845904523 1000000000000000000 999999999999999998 12193209765583 12193209765584 12193209765585 1 2 3 4 5 6 7

Sample Output 4

2

Sample Input 5

1 1 1 1
1000000000000000000

Sample Output 5

0