Emergency room: who gets the next doctor?

A busy emergency room in Johannesburg has K identical doctors. Patients arrive at known times and each needs a known treatment time. Whenever a doctor becomes free (or a patient arrives while a doctor is idle), the doctor takes the waiting patient with the highest severity (5 is most severe, 1 is least). If severities tie, the patient who arrived earlier goes first, and if arrival times also tie, the smaller patient id goes first. A patient is only waiting once their arrival time has been reached, and treatment is never interrupted. Times are in minutes.

Task: the first line holds K and n (1 ≤ K ≤ 10, 1 ≤ n ≤ 100). Each of the next n lines holds id arrival duration severity (ids are 1..n, in increasing order of id; arrival times are non-decreasing). Print n lines: for each patient in input order, the minute at which treatment starts. Then print one final line with the largest waiting time (start minus arrival) among all patients.