$N$ $(1 \le N \le 50,000)$ Kühe, nummeriert $1,\ldots,N$, fahren in eigenen Autos auf einer Autobahn in Cowtopia. Kuh $i$ kann jede der $M$ Spuren $(1 \le M \le N)$ nehmen, Höchstgeschwindigkeit $S_{i}$ $(1 \le S_{i} \le 1,000,000)$ km/h.

Nach schlechten Fahrerlebnissen hassen sie Kollisionen und vermeiden sie mit großen Anstrengungen. Für jede Kuh davor auf der Autobahn reduziert $i$ um $D$ $(0 \le D \le 5,000)$ km/h, niemals unter $0$. Bei $K$ davor fährt sie $\max(S_i - D K, 0)$. Auch wenn schneller als direkt davor, sind die Abstände groß genug, dass nach dem Bremsen kein Unfall passiert.

Cowtopia verlangt mindestens $L$ $(1 \le L \le 1,000,000)$ km/h, weshalb einige unter diesen Regeln nicht fahren können. Berechne die maximale Zahl gesetzestreu fahrender Kühe.

Eingabe

• Zeile $1$: durch Leerzeichen getrennte ganze Zahlen $N$, $M$, $D$, $L$.

• Zeilen $2,\ldots,N+1$: Zeile $i+1$ gibt die Anfangsgeschwindigkeit von $i$ als ganze Zahl $S_{i}$.

Ausgabe

• Zeile $1$: eine ganze Zahl, maximal fahrende Kühe.

Beispiele

Eingabe 1

3 1 1 5
5
7
5

Ausgabe 1

2

Hinweis

Drei Kühe, eine Spur, Reduktion $1$, Minimum $5$.

Zwei sind möglich: eine beliebige mit $5$ zuerst, die mit $7$ als zweite.

Aufgabenautor: Neal Wu, 2007