Les $N$ vaches de Farmer John $(1 \le N \le 50,000)$ broutent le long d’une clôture unidimensionnelle. La vache $i$ se trouve à la position $x(i)$ et a une taille $h(i)$ ($1 \le x(i),h(i) \le 10^9$).

Une vache se sent «à l’étroit» si une autre vache au moins deux fois plus haute se trouve à sa gauche à une distance d’au plus $D$, et si une telle vache se trouve aussi à sa droite à une distance d’au plus $D$ ($(1 \le D \le 1,000,000,000)$). Ces vaches produisent moins de lait ; Farmer John veut donc les compter. Aidez-le.

Entrée

• Ligne 1 : deux entiers $N$ et $D$.
• Lignes $2..1+N$ : la ligne $i+1$ contient les entiers $x(i)$ et $h(i)$. Les positions des $N$ vaches sont distinctes.

Sortie

• Ligne 1 : nombre de vaches à l’étroit.

Exemples

Entrée 1

6 4
10 3
6 2
5 3
9 7
3 6
11 2

Sortie 1

2

Remarque

Il y a 6 vaches, avec un seuil de distance de 4 pour se sentir à l’étroit. La vache n°1 est à la position $x=10$ et a une taille $h=3,$, et ainsi de suite.

Les vaches aux positions $x=5$ et $x=6$ sont toutes deux à l’étroit.

Auteur du problème : Brian Dean, 2013