Boss xnby owns a company, as you know, in the company there are lots of jobs to do. Each job J has a processing requirement pj (denoting the number of machine days required to complete the job), a release date rj (representing the beginning of the day when job j becomes available for processing), and a due date dj ≥ rj + pj (representing the beginning of the day by which the job must be completed). What could we do when facing so many jobs? Thank goodness, in xnby’s company, there are some parallel machines can do these jobs. Since a machine can work on only one job at a time and each job can be processed by at most one machine at a time. And preemptions(i.e., we can interrupt a job and process it on different machines on different days) is allowed. Now xnby can use these parallel machines to process these boring jobs, but he also needs to determine a feasible schedule that completes all jobs before their due dates or show no such schedule exist. Xnby is a boss, he is a big shot, he had no time to do with these trivial things, so he arranged for you to do this task.
For each test cases:
Two integers J and M (J ≤ 100, M ≤ 100) denote jobs and machines respectively.
In the following J lines(each job one line, in ascending order), each line contains three integers p, r, d (p ≤ 100,r ≤ 100 and d ≤ 200) denote processing requirement, release date and due date respectively.
1 4 3 2 3 5 1 1 4 2 3 7 4 5 9
Boss xnby is happy!