$N$ $(1 \le N \le 50,000)$ vacas numeradas $1,\ldots,N$ conducen coches separados por Cowtopia. La vaca $i$ elige cualquiera de $M$ carriles $(1 \le M \le N)$ con velocidad máxima $S_{i}$ $(1 \le S_{i} \le 1,000,000)$ km/h.

Tras malas experiencias odian colisiones y toman grandes medidas. Por cada vaca delante en la autopista, $i$ reduce $D$ $(0 \le D \le 5,000)$ km/h, nunca bajo $0$. Con $K$ delante va a $\max(S_i - D K, 0)$. Aunque más rápida que la inmediatamente anterior, hay suficiente distancia para evitar choques tras reducir.

Cowtopia exige al menos $L$ $(1 \le L \le 1,000,000)$ km/h, por lo que algunas no pueden usar la autopista siguiendo las reglas. Calcula el máximo que respeta la ley.

Entrada

• Línea $1$: enteros $N$, $M$, $D$, $L$ separados por espacios.

• Líneas $2,\ldots,N+1$: línea $i+1$ da la velocidad inicial de $i$ con entero $S_{i}$.

Salida

• Línea $1$: entero, máximo número que usa la autopista.

Ejemplos

Entrada 1

3 1 1 5
5
7
5

Salida 1

2

Nota

Tres vacas, un carril, reducción $1$, mínimo $5$.

Pueden dos: cualquiera de velocidad $5$ primero, la de $7$ segunda.

Autor del problema: Neal Wu, 2007