Après une épidémie de la maladie bovine très contagieuse COWVID-19, Farmer John s’inquiète pour ses vaches.

Malgré ses efforts pour faire pratiquer la « distanciation sociale » à ses $N$ vaches ($1 \leq N \leq 1000$), beaucoup ont été infectées. Numérotées $1 \ldots N$, elles se trouvent à des points distincts d’un long chemin, essentiellement une droite numérique ; la vache $i$ est en $x_i$. Il existe un rayon $R$ tel que toute vache à distance au plus $R$, limite comprise, d’une vache infectée soit infectée à son tour, puis transmette aux autres à distance au plus $R$, et ainsi de suite.

Farmer John ignore la valeur exacte de $R$, mais connaît les vaches infectées. Déterminez le nombre minimal possible de vaches infectées au départ.

Entrée

La première ligne contient $N$. Chacune des $N$ suivantes décrit une vache par deux entiers $x$, $s$ : sa position $x$ ($0 \leq x \leq 10^6$), et $s=0$ si elle est saine, $s=1$ si elle est malade. Au moins une est malade, et toutes celles susceptibles de le devenir par propagation le sont déjà.

Sortie

Affichez le nombre minimal de vaches qui pouvaient être malades avant toute propagation.

Exemples

Entrée 1

6
7 1
1 1
15 1
3 1
10 0
6 1

Sortie 1

3

Remarque

Ici $R<3$, sinon la vache en $7$ aurait infecté celle en $10$. Au moins $3$ étaient donc malades au départ : une des deux en $1$ et $3$, une des deux en $6$ et $7$, et celle en $15$.

Auteur du problème : Brian Dean