Социальная дистанция II
Фермер Джон обеспокоен здоровьем своих коров после вспышки очень заразной болезни крупного рогатого скота COWVID-19.
Несмотря на его лучшие попытки заставить своих n коров практиковать «социальное дистанцирование», многие из них, к сожалению, заболели этой болезнью. Каждая корова с номером 1 ... n стоит в разных точках на длинной тропе (по сути, это одномерная числовая линия), а корова i стоит в позиции x[i]. Фермер Джон знает, что существует радиус r, такой, что любая корова, стоящая в r единицах от зараженной коровы, также заразится (и затем передаст инфекцию другим коровам в пределах r единиц и так далее).
К сожалению, фермер Джон не знает точное значение r. Однако он знает, какая из его коров заражена. Учитывая эти данные, определите минимально возможное количество коров, изначально зараженных этим заболеванием.
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 1000). Каждая из следующих n строк описывает одну корову в виде двух целых чисел x и s, где x (0 ≤ x ≤ 10^6) - это позиция, а s равно 0 для здоровой коровы и 1 для больной коровы. По крайней мере одна корова заболела, и все коровы, которые могли заболеть в результате распространения болезни, теперь заболели.
Выходные данные
Выведите минимальное количество коров, которые изначально могли заболеть до распространения болезни.