Comme tous les adolescents, les jeunes vaches sont parfois emportées par des modes : cerceau, caillou de compagnie, Counterstrike, Pokemon, Rick Astley ou tatouages tribaux sur leurs pis.

Mathématiquement, l’attrait initial vaut $L$ ($1 \le L \le 50,000$). La résistance de la vache $i$ ($0 \le R_{i} \le 1,000,000$) indique combien de temps elle évite la mode avant de devoir participer. Si l’attrait atteint ou dépasse sa résistance, elle veut participer.

Chaque participante augmente l’attrait de $K$ ($1 \le K \le 2,500$) par pression des pairs.

Pour $N$ ($1 \le N \le 100,000$) vaches, trouvez le nombre de participantes.

Entrée

• Ligne $1$ : entiers $N$, $L$, $K$ séparés par des espaces.

• Lignes $2..N+1$ : ligne $i+1$, résistance de la vache $i$, entier $R_{i}$.

Sortie

• Ligne $1$ : entier, nombre final de participantes.

Exemples

Entrée 1

5 2 3
2
6
12
5
14

Sortie 1

3

Remarque

Cinq résistances $2,6,12,5,14$, attrait initial $2$ ; chaque participante ajoute $3$ à l’indice.

L’attrait $2$ attire la vache n°$1$ (résistance $2$) et devient $5$ ; n°$4$ ($5$) le porte à $8$, puis n°$2$ ($6$) à $11$. Ni n°$3$ ($12$) ni n°$5$ ($14$) ne suit ; total $3$.

Auteur du problème : Jarrah Lacko, 2009