시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 70 23 21 39.623%

문제

숭실대학교의 권욱제 교수는 새로운 강의를 준비하고 있다. 강의하기 귀찮은 권욱제 교수는 팀플 과제를 던져주고 대충 발표를 들으면서 한 학기 수업을 치우려고 한다. 그래서 수강생 $N$명을 몇 개의 팀으로 나누려고 한다. 그러나, 수강생들의 자존심이 세다. $i$번째 수강생은 팀원들 중 자신보다 키가 큰 사람이 $k_i$명 이상이면 강의실을 박차고 나갈 거라고 했다.

마음이 여린 권욱제 교수는 모든 수강생의 요구를 만족하도록 모든 수강생을 각각 하나의 팀에 넣으려 한다. 최소 몇 개의 팀을 만들어야 할까?

입력

첫 줄에 학생의 수 $N$이 주어진다.

이후 $N$개의 줄에 각 학생의 키 $h_i$와 최소 등수 $k_i$가 주어진다.

학생들의 키는 모두 다르다.

출력

만들어야 하는 팀의 개수의 최솟값을 출력한다.

제한

  • $1 \le N \le 500,000$
  • $1 \le h_i \le 500,000$, $1 \le k_i \le N$

예제 입력 1

5
172 1
161 2
188 4
154 2
180 1

예제 출력 1

3

키가 188cm, 154cm인 학생들을 한 팀으로, 키가 180cm, 161cm인 학생들을 한 팀으로, 키가 172cm인 학생을 혼자 팀으로 묶으면 총 3개의 팀을 구성할 수 있다. 더 적은 갯수의 팀으로 학생들을 묶을 수 있는 방법은 없다.