Problems
연예기획사인 한컴엔터테인먼트에서는 5개의 음악작업실을 갖추어놓고
작업을 원하는 제작자들로부터 작업을 원하는 시간대를 받아서 작업실을 사용할 수 있도록 배정하고 있다.
작업실은 한팀이 한번에 최대 10시간까지 사용할 수 있고 원하는 시간을 받으면
그 시간 이후부터 10시간 이내에 끝낼수 있도록 작업실을 배정하면 된다.
예를 들어 어떤 제작자가 3시부터 7시간동안 작업실을 사용하기 원한다면
3시이후부터 13시가 넘지 않는 시간에 끝낼 수 있도록
3시~10시, 4시~11시, 5시~12시, 6시~13시 이렇게 4가지 방법중 한가지로 배정이 가능하다.
작업실을 여러개 운영하게 되면 작업실을 세팅하기 위해 많은 비용이 들기 때문에
가능하면 최소의 작업실 만으로 모든 신청을 배정해 주려고 한다.
최소 몇 개의 작업실이 필요한지 구하는 프로그램을 작성하라.
Input
입력의 처음에는 테스트케이스의 수 T가 입력된다. (1 <= T <= 5)
각 테스트 케이스의 첫 번째 줄에는 작업실을 신청한 제작자의 수 N이 입력된다. (1 <= N <= 1000)
다음 줄부터 N개의 줄에 걸쳐 작업실을 원하는 시간대(si)와 사용시간(ti)이 시간대를 기준으로 오름차순으로 정렬되어 입력된다. (1 <= si <= 5000, 1 <= ti <= 10)
Output
각 줄에 테스트 케이스마다 필요로 하는 최소 작업실의 개수를 출력한다.
작업실 5개로도 모든 신청을 배정할 수 없을 때에는 -1을 출력한다.
Example
1
2
2 7
3 8
2
You must sign in to write code.