Sau đợt bùng phát bệnh bò rất dễ lây COWVID-19, Farmer John lo cho sức khỏe đàn bò.

Dù cố hết sức để $N$ con bò ($1 \leq N \leq 1000$) thực hiện “giãn cách xã hội”, nhiều con vẫn nhiễm bệnh. Đánh số $1 \ldots N$, chúng đứng tại các điểm khác nhau trên đường dài, về cơ bản là trục số một chiều; bò $i$ đứng ở $x_i$. Có bán kính $R$ sao cho bò cách bò nhiễm không quá $R$ cũng nhiễm, rồi lây tiếp cho các bò cách nó không quá $R$, và cứ thế.

Ông không biết chính xác $R$, nhưng biết bò nào đã nhiễm. Hãy tìm số bò nhiễm từ đầu nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu chứa $N$. Mỗi dòng trong $N$ dòng tiếp theo mô tả một bò bằng số nguyên $x$, $s$: vị trí $x$ ($0 \leq x \leq 10^6$), và $s=0$ nếu khỏe hoặc $s=1$ nếu bệnh. Ít nhất một con bệnh và tất cả bò có thể mắc do lây lan đều đã mắc.

Dữ liệu ra

In số bò nhỏ nhất có thể mắc bệnh trước mọi sự lây lan.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3

Ghi chú

Ở đây $R<3$, nếu không bò tại $7$ đã lây cho bò tại $10$. Vì vậy ít nhất $3$ con mắc từ đầu: một trong hai con tại $1$ và $3$, một trong hai con tại $6$ và $7$, và con tại $15$.

Tác giả bài toán: Brian Dean