Nông dân John lo lắng cho sức khỏe của những con bò sau khi căn bệnh truyền nhiễm rất mạnh ở bò COWVID-19 bùng phát.

Bất chấp nỗ lực hết sức để \(N\) con bò của mình (\(1 \leq N \leq 1000\)) thực hiện "giãn cách xã hội", thật không may là nhiều con vẫn mắc bệnh. Những con bò được đánh số thuận tiện từ \(1 \ldots N\) và mỗi con đứng tại một điểm riêng biệt dọc theo một con đường dài (về cơ bản là một trục số một chiều), trong đó bò \(i\) đứng tại vị trí \(x_i\). Nông dân John biết rằng tồn tại một bán kính \(R\) sao cho bất kỳ con bò nào đứng cách một con bò nhiễm bệnh không quá \(R\) đơn vị cũng sẽ bị lây nhiễm (sau đó lại truyền bệnh cho những con bò khác cách nó không quá \(R\) đơn vị, và cứ tiếp tục như vậy).

Đáng tiếc là Nông dân John không biết chính xác \(R\). Tuy nhiên, ông biết những con bò nào đã bị nhiễm bệnh. Với dữ liệu này, hãy xác định số bò ít nhất có thể đã bị nhiễm bệnh từ ban đầu.

Dữ liệu vào

Tệp socdist2.in:

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một con bò bằng hai số nguyên \(x\) và \(s\), trong đó \(x\) là vị trí của con bò (\(0 \leq x \leq 10^6\)), còn \(s\) bằng 0 nếu bò khỏe mạnh và bằng 1 nếu bò bị bệnh. Có ít nhất một con bò bị bệnh, và tất cả những con bò có khả năng bị lây bệnh do bệnh lan truyền thì giờ đây đều đã bị bệnh.

Dữ liệu ra

Tệp socdist2.out:

In ra số bò ít nhất có thể đã bị bệnh từ ban đầu, trước khi bệnh bắt đầu lan truyền.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

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

3

Nguồn

USACO 2020 US Open Contest, Bronze — Social Distancing II

Tác giả bài: Brian Dean.