// Arup Guha
// 5/25/2013
// Solution to 2013 Rocky Mountain Regional Problem J: Emergency Room

import java.util.*;

public class j {

	// Last time for an event.
	final public static int MAX = 51000;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numDocs = stdin.nextInt();
		int startTime = stdin.nextInt();
		int loop = 1;

		// Go through each case.
		while (numDocs != 0) {

			// Priority Queue for docs
			// Priority Queue for patient events.
			// Sim: in time.
			ArrayList<patient> origList = new ArrayList<patient>();

			// Read in data for this case.
			int arrival = stdin.nextInt();
			while (arrival != -1) {

				int priority = stdin.nextInt();
				int duration = stdin.nextInt();
				ArrayList<treatment> maladies = new ArrayList<treatment>();

				while (priority != 0 || duration != 0) {
					maladies.add(new treatment(priority, duration));
					priority = stdin.nextInt();
					duration = stdin.nextInt();
				}

				origList.add(new patient(arrival, maladies));
				arrival = stdin.nextInt();
			}

			System.out.println("Case "+loop+":");
			process(numDocs, startTime, origList);

			// Go to next case.
			numDocs = stdin.nextInt();
			startTime = stdin.nextInt();
			loop++;
		}

	}

	// Processes one case.
	public static void process(int numDocs, int startTime, ArrayList<patient> origList) {

		PriorityQueue<Integer> docs = new PriorityQueue<Integer>();
		PriorityQueue<patient> sick = new PriorityQueue<patient>();
		LinkedList[] freeAt = new LinkedList[MAX];
		for (int i=0; i<MAX; i++)
			freeAt[i] = new LinkedList<patient>();

		ArrayList<output> list = new ArrayList<output>();
		int curPatient = 0;

		// Step through time increments. (Note: I am skeptical that my solution is always correct. I
		// think their data might have been weak. I think there's a way to exceed 51000 for a patient.)
		for (int t=0; t<MAX; t++) {

			// Add in all the doctors, ready to see patients.
			if (t == startTime) {
				for (int i=0; i<numDocs; i++)
					docs.add(t);
			}

			// Add back new patients from doctors rooms.
			while (freeAt[t].size() > 0) {
				patient p = (patient)freeAt[t].poll();
				if (p.needsTreatment())
					sick.add(p);
				else
					list.add(new output(p.arrival, t));
			}

			// Add new patient at this time, if necessary.
			if (curPatient < origList.size() && origList.get(curPatient).arrival == t) {
				sick.add(origList.get(curPatient));
				curPatient++;
			}

			// Look for free docs
			while (docs.size() > 0 && docs.peek() <= t && sick.size() > 0) {

				// Get the doc and the patient.
				int readyDoc = docs.poll();
				patient p = sick.poll();

				// Treat the patient and add the doc back to the queue when she's ready.
				p.treat(t);
				docs.add(p.freeAt);

				// Place this patient in the linked list based on when they'll be free to get the next treatment.
				freeAt[p.freeAt].add(p);

			}
		}

		// sim is over...output
		Collections.sort(list);
		for (int i=0; i<list.size(); i++)
			System.out.println(list.get(i));
	}
}

class treatment {

	public int priority;
	public int duration;

	public treatment(int a, int b) {
		priority = a;
		duration = b;
	}
}

class patient implements Comparable<patient> {

	public int arrival;
	public ArrayList<treatment> maladies;
	public int numTreated;
	public int freeAt;

	public patient(int arrive, ArrayList<treatment> list) {
		arrival = arrive;
		maladies = list;
		numTreated = 0;
		freeAt = arrival;
	}

	// Treat the current malady starting at startTime.
	public void treat(int startTime) {
		freeAt = startTime + maladies.get(numTreated).duration;
		numTreated++;
	}

	// Used for priority queue in simulation.
	public int compareTo(patient other) {

		if (this.maladies.get(numTreated).priority != other.maladies.get(other.numTreated).priority)
			return other.maladies.get(other.numTreated).priority - this.maladies.get(numTreated).priority;
		return this.arrival - other.arrival;
	}

	public boolean needsTreatment() {
		return numTreated < maladies.size();
	}
}

// Just to sort output - problem can be solved without this, since simulation fixes output order anyway.
class output implements Comparable<output> {

	public int ID;
	public int done;

	public output(int a, int b) {
		ID = a;
		done = b;
	}

	// Fits output format.
	public String toString() {
		return "Patient "+ID+" released at clock = "+done;
	}

	public int compareTo(output other) {
		if (this.done != other.done)
			return this.done - other.done;
		return this.ID - other.ID;
	}
}