레이팅 미적용설명
베시는 농부 존에게서 L분 동안 (1 <= L <= 100,000,000) 숨고 싶은데, 그동안 영화를 끊김 없이 계속 보려고 한다. 선택할 수 있는 영화는 N편이며 (1 <= N <= 20), 각 영화에는 상영 시간과 하루 동안의 상영 시작 시각들이 정해져 있다. 베시는 어떤 상영 중이든 아무 때나 입장하고 퇴장할 수 있지만, 같은 영화를 두 번 보고 싶지는 않으며, 현재 보고 있는 상영과 시간이 겹치는 같은 영화의 다른 상영으로 옮겨 갈 수도 없다.
베시가 시각 0부터 시각 L까지 영화를 끊김 없이 볼 수 있는지 판단하시오. 가능하다면, 봐야 하는 영화 수의 최솟값을 구하시오.
제약
입력 형식
첫째 줄에 N과 L이 주어진다.
다음 N개의 줄 각각에는 영화 하나가 주어진다: 정수 상영 시간 D (1 <= D <= L)와 상영 횟수 C (1 <= C <= 1000), 이어서 상영 시작 시각을 나타내는 0..L 범위의 정수 C개가 주어진다 (서로 다르며 증가하는 순서).
출력 형식
베시가 목표를 달성하기 위해 봐야 하는 영화 수의 최솟값을 나타내는 정수 하나를 출력한다. 불가능하면 -1을 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
movie.in · 출력을 쓸 파일 movie.out예제 1
입력
4 100
50 3 15 30 55
40 2 0 65
30 2 20 90
20 1 0출력
3설명
Output details: Watch movie 4 (0-20), movie 1 (20-65), then movie 2 (65-100).
문제 정보
태그