문제
농부 창호는 소로나 바이러스(COWVID-19) 예방을 위해 자신의 소들에게 사회적 거리두기를 실천하도록 가르치고 있다.
그럼에도 불구하고, 몇몇 소들이 벌써 바이러스에 감염되어버렸다.
소들의 거주지는 직선 위에 있으며, 가장 왼쪽부터 차례대로 0, 1, 2……의 주소를 가진다.
농부 창호에게는 N마리의 소가 있으며, 이들은 서로 다른 거주지에 산다.
전체 N마리의 소 중, M마리가 최초로 감염되었으며,
감염된 소로부터 R만큼 떨어진 곳에 사는 소들도 모두 연쇄적으로 감염되었다
(즉 최초 감염자뿐만 아니라, 2차, 3차 감염자 역시 범위 R 내에 거주하는 다른 소를 감염시켰다).
문제는, 농부 창호는 최초 감염자 수인 M의 값도, 감염 범위 R값도 모른다는 것이다.
이에 농부 창호는 현 상황을 바탕으로 최초 감염자 수인 M이 최소 몇인지 알아내려고 한다.
이를 도와주는 프로그램을 작성하라.
입력
첫 줄에 N이 주어진다. (1≤N≤1,000)
다음 N줄에 걸쳐서, 각 소가 사는 거주지의 주소인 x와 감염 여부인 y가 공백을 사이에 두고 주어진다.
y는 0또는 1이며, 0일 경우 감염되지 않은 소를, 1일 경우 감염된 소를 뜻한다. (0≤x≤1,000,000)
주어진 모든 수는 정수이다.
출력
최초 감염자 수의 최소값을 출력한다.
예제1
6
7 1
1 1
15 1
3 1
10 0
6 1
3
좌표 7에 위치한 소가 좌표 10에 있는 소를 감염시키지 않았다는 사실을 토대로, R<3임을 알 수 있다.
이 조건에서, 적어도 3마리의 소는 최초 감염자임을 알 수 있다:
1)좌표 1에 사는 소 혹은 좌표 3에 사는 소
2)좌표 6에 사는 소 혹은 좌표 7에 사는 소
3)좌표 15에 사는 소