시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 770 | 220 | 178 | 31.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$을 출력한다.
5 5 4 6 2 2 1 9 1 10 3
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 |
3 5 3 3 5 4 3
-1
Contest > 보라매컵 > 제1회 보라매컵 예선 C번