시간 외 근무 멈춰!

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N개의 작업마다 마감일과 필요한 작업일이 주어질 때, 모든 작업을 기한 안에 끝내는 데 필요한 최소 야근 일수를 구합니다. 불가능하면 -1을 출력합니다.

난이도: 보통10점 중 5점
유형: 그리디, 이분 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

개발 프로젝트는 총 $N$ 개의 작업으로 이루어져 있다. 각 작업 $i$ 에는 $t_i$ 일의 근무일이 필요하며, 프로젝트가 시작한 뒤 $d_i$ 일이 지나기 전에 끝내야 한다. 평시 근무만으로는 모든 작업을 제때 끝내기 어려워 보여서, 준민이는 개인 정비시간을 포기하고 시간 외 근무를 하려고 한다.

프로젝트는 월요일부터 시작한다. 평시 근무는 월요일부터 금요일까지만 진행한다. 시간 외 근무는 요일과 관계없이 매일 최대 한 번씩 진행할 수 있으며, 시간 외 근무를 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$ 을 출력한다.

예제2

예제 1
입력
```
5
5 4
6 2
2 1
9 1
10 3
```
예상 출력
```
3
```
예제 2
입력
```
3
5 3
3 5
4 3
```
예상 출력
```
-1
```