Plan King
Time limit3sMemory limit1024 MB
Given N fixed, non-overlapping meetings in a 1440-minute day and K task durations, decide whether all K tasks can be squeezed into the free gaps.
- Level
Medium4 of 10
- Topics
- Greedy, Sorting, Implementation, Brute force
- Solved
- No attempts yet
Problem
Bareum keeps to the plans written in his diary every day and leads a well-ordered life. Today he is planning tomorrow's schedule.
Bareum has a lot to do, such as study sessions, live lectures, and club activities, so some time is already taken up by these fixed commitments.
On top of that, Bareum still has many other things to do, such as assignments and dating! Our job is to tell him whether the plan he made can actually be carried out.
Bareum is strong-willed and highly driven, so:
- Once he starts a task, he must see it through to the end.
- He can start a new task at the same moment another one ends.
Input
The first line gives the number of already fixed schedules N (1 ≤ N ≤ 11) and the number of tasks Bareum must additionally do tomorrow K (1 ≤ K ≤ 12).
Each of the next N lines gives the start time s (0 ≤ s < 1440) and end time e (s < e ≤ 1440) of one fixed schedule.
The day starts at time 0 and ends at time 1440, the schedules do not overlap, and they are given in chronological order.
The last line gives the times T1, T2, ..., TK needed to do the K tasks Bareum planned, separated by spaces.
Each task time Ti is an integer between 1 and 1440, and the sum of T1, T2, ..., TK does not exceed 1440.
Output
Print GOOD if Bareum can carry out all the tasks he planned, and BAD otherwise.