$N$ $(1 \le N \le 50,000)$ krów o numerach $1,\ldots,N$ jedzie osobnymi autami autostradą w Cowtopia. Krowa $i$ wybiera dowolny z $M$ pasów $(1 \le M \le N)$, maksimum $S_{i}$ $(1 \le S_{i} \le 1,000,000)$ km/h.

Po złych doświadczeniach nienawidzą kolizji i usilnie unikają ich. Za każdą krowę przed nią na autostradzie $i$ zwalnia o $D$ $(0 \le D \le 5,000)$ km/h, nie poniżej $0$. Z $K$ przed nią jedzie $\max(S_i - D K, 0)$. Nawet szybsza od bezpośrednio poprzedniej ma wystarczający odstęp, by po zwolnieniu nie zderzyć się.

Cowtopia wymaga co najmniej $L$ $(1 \le L \le 1,000,000)$ km/h, więc niektóre nie mogą jechać zgodnie z zasadami. Oblicz maksimum przestrzegające prawa.

Wejście

• Wiersz $1$: całkowite $N$, $M$, $D$, $L$ oddzielone spacjami.

• Wiersze $2,\ldots,N+1$: wiersz $i+1$ opisuje początkową prędkość $i$ całkowitym $S_{i}$.

Wyjście

• Wiersz $1$: całkowite, maksymalna liczba krów na autostradzie.

Przykład

Wejście 1

3 1 1 5
5
7
5

Wyjście 1

2

Uwagi

Trzy krowy, jeden pas, spadek $1$, minimum $5$.

Mogą dwie: dowolna z prędkością $5$ pierwsza, z $7$ druga.

Autor zadania: Neal Wu, 2007