Minimum Initial Infected Cows

Due to the outbreak of the highly contagious bovine disease COWVID-19, Farmer John is extremely worried about the health of his cows. There are N cows (where \(1\le N\le1000\)) located at distinct positions along a long straight road (modeled as a one‐dimensional number line). The \(i^{th}\) cow is at position \(x_i\).

It is known that there exists a transmission radius \(R\) such that any cow within a distance \(\le R\) from an infected cow will also get infected (and then will pass the infection on to any cow within \(R\) units, and so on). Unfortunately, Farmer John does not know the exact value of \(R\); he only knows which cows ended up infected.

Your task is to determine the minimum number of cows that could have been initially infected such that, after the disease spreads with some possible radius \(R\) (chosen to be as high as possible while still maintaining the observed pattern), the set of infected cows is exactly those observed.

Hint: For every healthy cow, to remain uninfected, the transmission radius must satisfy
\(R<\min_{\text{infected } i}|x_i-h|\) for that healthy cow \(h\). Let the maximum possible consistent \(R\) be \(R_{max}=\min_{\text{healthy }h}\;\min_{\text{infected } i}|x_i-h|\). Then, among the infected cows sorted by position, any two consecutive infected cows can be in the same infection chain if and only if their distance is strictly less than \(R_{max}\).

inputFormat

The first line contains a single integer \(N\). The following \(N\) lines each contain two integers \(x\) and \(s\), where \(x\) is the position of the cow and \(s\) is its status (1 if the cow is infected and 0 if it is healthy).

It is guaranteed that all positions \(x\) are distinct.

outputFormat

Output a single integer: the minimum number of cows that must have been initially infected.

sample

5
1 1
3 0
6 1
10 0
12 1

3