$N$ $(1 \le N \le 50,000)$ vacas numeradas $1,\ldots,N$ conduzem carros separados numa autoestrada de Cowtopia. A vaca $i$ escolhe qualquer das $M$ faixas $(1 \le M \le N)$, com velocidade máxima $S_{i}$ $(1 \le S_{i} \le 1,000,000)$ km/h.

Após más experiências odeiam colisões e fazem grandes esforços. Por cada vaca à frente na autoestrada, $i$ reduz $D$ $(0 \le D \le 5,000)$ km/h, nunca abaixo de $0$. Com $K$ à frente vai a $\max(S_i - D K, 0)$. Mesmo mais rápida que a imediatamente à frente, há distância suficiente para evitar colisões após reduzir.

Cowtopia exige pelo menos $L$ $(1 \le L \le 1,000,000)$ km/h, pelo que algumas não podem usar a autoestrada segundo as regras. Calcule o máximo que respeita a lei.

Entrada

• Linha $1$: inteiros $N$, $M$, $D$, $L$ separados por espaços.

• Linhas $2,\ldots,N+1$: linha $i+1$ dá velocidade inicial de $i$ pelo inteiro $S_{i}$.

Saída

• Linha $1$: inteiro, máximo de vacas na autoestrada.

Exemplos

Entrada 1

3 1 1 5
5
7
5

Saída 1

2

Nota

Três vacas, uma faixa, redução $1$, mínimo $5$.

Podem duas: qualquer uma a $5$ primeiro, a de $7$ segunda.

Autor do problema: Neal Wu, 2007