$N$ $(1 \le N \le 50,000)$ mucche numerate $1,\ldots,N$ guidano auto separate in autostrada a Cowtopia. La mucca $i$ sceglie una qualsiasi delle $M$ corsie $(1 \le M \le N)$, velocità massima $S_{i}$ $(1 \le S_{i} \le 1,000,000)$ km/h.

Dopo brutte esperienze odiano collisioni e prendono grandi precauzioni. Per ogni mucca davanti in autostrada, $i$ riduce $D$ $(0 \le D \le 5,000)$ km/h, mai sotto $0$. Con $K$ davanti va a $\max(S_i - D K, 0)$. Anche se più veloce di quella subito davanti, le distanze bastano a evitare incidenti dopo la riduzione.

Cowtopia impone almeno $L$ $(1 \le L \le 1,000,000)$ km/h, quindi alcune non possono viaggiare seguendo le regole. Calcola il massimo che rispetta la legge.

Input

• Riga $1$: interi $N$, $M$, $D$, $L$ separati da spazi.

• Righe $2,\ldots,N+1$: riga $i+1$ dà velocità iniziale di $i$ con intero $S_{i}$.

Output

• Riga $1$: intero, massimo di mucche in autostrada.

Esempi

Input 1

3 1 1 5
5
7
5

Output 1

2

Nota

Tre mucche, una corsia, riduzione $1$, minimo $5$.

Possono due: una qualunque a $5$ prima, quella a $7$ seconda.

Autore del problema: Neal Wu, 2007