$N$ $(1 \le N \le 50,000)$ vaches, numérotées $1,\ldots,N$, conduisent chacune une voiture sur une autoroute de Cowtopia. La vache $i$ choisit parmi $M$ voies $(1 \le M \le N)$, à vitesse maximale $S_{i}$ $(1 \le S_{i} \le 1,000,000)$ km/h.
Après de mauvaises expériences, elles détestent les collisions et prennent de grandes précautions. Pour chaque vache devant elle sur l’autoroute, $i$ réduit sa vitesse de $D$ $(0 \le D \le 5,000)$ km/h, sans descendre sous $0$. Avec $K$ devant, c’est $\max(S_i - D K, 0)$. Même plus rapide que celle juste devant, l’espacement suffit pour éviter les accidents après cette réduction.
La loi de Cowtopia impose au moins $L$ $(1 \le L \le 1,000,000)$ km/h ; certaines ne peuvent donc rouler avec ces règles. Calculez le maximum de vaches pouvant respecter la loi.
Entrée
Ligne $1$ : entiers $N$, $M$, $D$, $L$ séparés par des espaces.
Lignes $2,\ldots,N+1$ : la ligne $i+1$ décrit la vitesse initiale de $i$ par l’entier $S_{i}$.
Sortie
- Ligne $1$ : un entier, le maximum de vaches sur l’autoroute.
Exemples
Entrée 1
3 1 1 5 5 7 5
Sortie 1
2
Remarque
Trois vaches, une voie, réduction $1$, minimum $5$.
Deux sont possibles : l’une des vaches à $5$ d’abord, celle à $7$ ensuite.
Auteur du problème : Neal Wu, 2007