#agc011a. [agc011_a]Airport Bus

[agc011_a]Airport Bus

問題文

高橋空港には,毎日飛行機で NN 人の乗客が到着します. ii 番目の乗客は時刻 TiT_i に到着します.

高橋空港に到着する乗客は全員バスで市内へ移動します.どのバスも定員は CC 人であり,CC 人以下の乗客を乗せることができます. 飛行機の乗客は,飛行機の到着時刻よりも早く出発するバスには乗ることができません. また,飛行機の到着時刻から KK の時間が経過した後にもバスに乗れていないと,怒り出してしまいます. そのため,ii 番目の乗客は,出発時刻が TiT_i 以上 Ti+KT_i + K 以下であるようなバスに乗れるようにしないといけません.

この条件のもとで,うまくバスの出発時刻を定めるとき,必要なバスの数の最小値を求めてください. ただし,バスの出発時刻は必ずしも整数である必要はなく,同じ時刻に出発するバスが複数あってもかまいません.

制約

  • 2leqNleq1000002 \\leq N \\leq 100000
  • 1leqCleq1091 \\leq C \\leq 10^9
  • 1leqKleq1091 \\leq K \\leq 10^9
  • 1leqTileq1091 \\leq T_i \\leq 10^9
  • C,K,TiC, K, T_i は整数

入力

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

NN CC KK T1T_1 T2T_2 :: TNT_N

出力

必要なバスの数の最小値を出力せよ.


入力例 1

5 3 5
1
2
3
6
12

出力例 1

3

例えば,時刻 4.54.5, 66, 1212 にバスを出発させ,次のように乗客をバスに乗せるとよいです.

  • 時刻 4.54.5 に出発するバスには,時刻 2,32, 3 に到着する乗客を乗せる.
  • 時刻 66 に出発するバスには,時刻 1,61, 6 に到着する乗客を乗せる.
  • 時刻 1212 に出発するバスには,時刻 1212 に到着する乗客を乗せる.

入力例 2

6 3 3
7
6
2
8
10
6

出力例 2

3