$N$ $(1 \le N \le 50,000)$ 頭、番号 $1,\ldots,N$ の牛がそれぞれ車で Cowtopia の高速道路を走ります。牛 $i$ は $M$ 車線 $(1 \le M \le N)$ のどれでも使え、最高速度は $S_{i}$ $(1 \le S_{i} \le 1,000,000)$ km/時です。

以前の悪い運転経験から衝突を嫌い、徹底して避けます。道路上で前方にいる一頭につき牛 $i$ は $D$ $(0 \le D \le 5,000)$ km/時減速し、$0$ 未満にはしません。前に $K$ 頭なら $\max(S_i - D K, 0)$ です。直前の牛より速くても間隔が十分なので、この減速で衝突しません。

Cowtopia の法律は最低 $L$ $(1 \le L \le 1,000,000)$ km/時を要求し、規則を守ると走れない牛もいます。最低速度法を守って走れる最大頭数を計算してください。

入力

• $1$ 行目：空白区切りの整数 $N$、$M$、$D$、$L$。

• $2,\ldots,N+1$ 行目：$i+1$ 行目に牛 $i$ の初期速度の整数 $S_{i}$。

出力

• $1$ 行目：走れる最大頭数の整数。

入出力例

入力 1

3 1 1 5
5
7
5

出力 1

2

注記

三頭、一車線、減速 $1$、最低速 $5$ です。

速度 $5$ のどちらかを最初、$7$ を二番目にすれば二頭走れます。

問題作成者：Neal Wu、2007