Emergency Room

An emergency room is staffed by several doctors. When a patient arrives, their arrival time is recorded and they are assigned a number of treatments. Each treatment has a priority and a duration. For any single patient, the priorities of successive treatments form a strictly decreasing sequence, such as 8, 5, 3 in the following example:

• Treatment 1: priority = 8, duration = 10
• Treatment 2: priority = 5, duration = 25
• Treatment 3: priority = 3, duration = 15

Every treatment must be performed by a doctor, but different treatments for the same patient need not be performed by the same doctor. A doctor can treat only one patient at any given time.

In the morning all doctors open their cubicles and become available at the same instant. Some patients may already have arrived by then, and others arrive later. Whenever a doctor becomes available, the patient in the waiting room whose next treatment has the highest priority is chosen and assigned to that doctor. Ties are broken by the earliest original arrival time. When more than one doctor is available, more than one patient may begin their next treatment at the same time.

When one of a patient's treatments finishes but treatments still remain, the patient returns to the waiting room and waits for their next turn. When all of a patient's treatments are complete, the patient is released from the emergency room.

The input contains data for several test cases. For each test case, the first line contains two positive integers: the number of doctors at the facility and the clock reading at which the doctors become available in the morning. Every time in the input is a single positive integer, in some unspecified unit, up to 1000.

The rest of each test case describes the patients. For each patient, the first line gives the arrival time. The following lines list that patient's pending treatments, one per line, each given as two positive integers: priority and duration. A patient's priorities are listed in strictly decreasing order. No two patients share the same arrival time, and patients are listed in increasing order of arrival time.

A line containing two 0s marks the end of one patient's data, a line containing -1 marks the end of a test case, and a final line containing two 0s marks the end of the input. Each test case has at most 500 doctors and at most 500 patients. The maximum priority and the maximum duration of any treatment is 100.

For each test case, first print the case number as Case X: (numbering starts at 1). Then print, for each patient, the time at which the patient can be released from the emergency room, formatted as Patient A released at clock = R, where A is the patient's arrival time and R is the release time. List patients in increasing order of release time; if several patients are released at the same time, list them in order of arrival time.