시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB77022017831.957%

문제

오늘도 여러 체계의 개발 임무를 열심히 수행 중인 준민이에게 갑자기 새로운 개발 프로젝트가 들어왔다. 해당 개발 프로젝트는 총 $N$개의 작업으로 이루어져 있으며, 각 작업은 $t_i$의 근무일이 필요하며 개발 프로젝트가 시작한 이후 $d_i$일이 지나기 전에 끝내야 한다. 그러나 평시 근무만으로는 모든 $N$개의 작업을 시간 내에 끝내기 힘들어 보였던 준민이는 개인 정비시간을 포기하며 시간 외 근무를 하고자 한다.

개발 프로젝트는 월요일부터 시작하며, 평시 근무는 월요일부터 금요일까지만 진행한다. 시간 외 근무는 요일과 관계없이 매일 최대 한 번씩만 진행할 수 있으며, 시간 외 근무를 $1$회 진행하면 $1$일치 업무를 끝마칠 수 있다.

준민이는 이를 토대로 효과적인 일정을 짜고 싶었지만, 이미 프로젝트로 너무 바빠진 준민이는 일정을 짤 시간조차 없는 상태이다. 바쁜 준민이를 위해, 모든 작업을 마감 기한 전까지 끝내고자 할 때 해야 하는 최소 시간 외 근무 일수를 알려주자.

입력

첫 번째 줄에 작업의 개수 $N$이 주어진다. $(1\leq N\leq 100\,000)$

두 번째 줄부터 $N+1$번째 줄까지, 각 작업의 마감 기한을 나타내는 정수 $d_i$와 작업에 걸리는 시간을 나타내는 정수 $t_i$가 공백으로 구분되어 주어진다. $(1\leq d_i,t_i\leq 100\,000)$

출력

모든 작업을 마감 기한 전까지 끝낼 수 있도록 하는 최소 시간 외 근무 일수를 출력한다.

만약 어떻게 해도 마감 기한 전까지 모든 작업을 끝낼 수 없다면, $-1$을 출력한다.

예제 입력 1

5
5 4
6 2
2 1
9 1
10 3

예제 출력 1

3

입력에서 주어진 순서대로 각각 $1$번 작업부터 $5$번 작업까지라고 할 때, 최적의 근무 일정 중 하나는 다음과 같다.

작업 일차 평시 근무 작업 번호 시간 외 근무 작업 번호
$1$일차 $1$ X
$2$일차 $3$ $2$
$3$일차 $1$ X
$4$일차 $1$ $2$
$5$일차 $1$ X
$6$일차 X X
$7$일차 X X
$8$일차 $5$ X
$9$일차 $4$ $5$
$10$일차 $5$ X

예제 입력 2

3
5 3
3 5
4 3

예제 출력 2

-1