Problem Description

Due to the outbreak of the highly contagious cow disease COWVID-19, Farmer John is very worried about the health of his cows.

Even though he has tried his best to make his $N$ cows ($1\le N\le 1000$) practice “social distancing”, many cows have unfortunately become infected.

The cows numbered $1\ldots N$ are located at distinct positions along a long straight road (equivalent to a one-dimensional number line). Cow $i$ is at position $x_i$. Farmer John knows that there exists a radius $R$ such that any cow within a distance of at most $R$ units from an infected cow will also become infected (and then it will infect cows within $R$ units of it, and so on).

Unfortunately, Farmer John does not know the exact value of $R$. He only knows which of his cows are infected. Given this information, find the minimum number of cows that were infected initially.

Input Format

The first line contains $N$. The next $N$ lines each contain two integers $x$ and $s$ describing a cow, where $x$ is its position ($0\le x\le 10^6$), and $s$ is $0$ for a healthy cow and $1$ for an infected cow. Also, all cows that could possibly be infected through the spread have already been infected.

Output Format

Output the minimum number of cows that were already infected before the disease started spreading.

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

3

Hint

Sample Explanation 1

In this example, we know that $R<3$, otherwise the cow at position $7$ would infect the cow at position $10$. Therefore, at least $3$ cows were infected initially: one of the two cows at positions $1$ and $3$, one of the two cows at positions $6$ and $7$, and the cow at position $15$.

Translated by ChatGPT 5