계획왕
시간 제한3초메모리 제한1024 MB
1440분 길이의 하루에 겹치지 않는 고정 일정 N개와 해야 할 작업 K개의 소요 시간이 주어질 때, 남는 빈 시간에 모든 작업을 배치할 수 있는지 판정한다.
문제
매일 다이어리에 세워 둔 계획을 지키며 바른 생활을 실천하는 바름이가 내일의 일정을 계획하고 있다.
바름이는 스터디, 실시간 강의, 동아리 등 할 일이 많아서, 일부 시간은 이미 해당 일들을 하는 데 고정적으로 쓰인다.
그런데 바름이에게는 위의 일 말고도 과제, 연애 등 해야 할 일이 많다! 우리가 해야 할 일은 바름이가 세운 계획이 실현 가능한지 알려주는 것이다.
바름이는 강단 있고 추진력이 뛰어나서,
- 한 가지 일을 시작하면 반드시 끝을 봐야 한다.
- 일이 종료됨과 동시에 새 일을 시작할 수 있다.
입력
첫째 줄에는 이미 고정된 일정의 개수 N(1 ≤ N ≤ 11), 바름이가 내일 추가적으로 해야 할 일의 개수 K(1 ≤ K ≤ 12)가 주어진다.
둘째 줄부터 N개의 줄에는 각 줄마다 고정된 일정의 시작 시각 s(0 ≤ s < 1440)와 종료 시각 e(s < e ≤ 1440)가 주어진다.
하루의 시작 시각은 0, 종료 시각은 1440이며, 각 일정은 겹치지 않고 시간 순으로 주어진다.
마지막 줄에는 바름이가 계획한 일 K개를 하는 데 걸리는 시간 T1, T2, ..., TK가 공백을 사이에 두고 주어진다.
각 일을 하는 데 걸리는 시간 Ti는 1 이상 1440 이하의 정수이며, T1, T2, ..., TK의 합은 1440을 넘지 않는다.
출력
바름이가 계획한 일을 모두 수행하는 것이 가능하면 GOOD, 그렇지 않으면 BAD를 출력한다.