응급실

응급실에는 여러 명의 의사가 근무한다. 환자가 응급실에 도착하면 도착 시각이 기록되고, 각 환자에게는 여러 개의 치료가 배정된다. 각 치료에는 우선순위와 소요 시간이 있다. 한 환자가 받을 연속된 치료들의 우선순위는 항상 강하게 감소하는 수열을 이룬다. 예를 들어 아래처럼 8, 5, 3으로 감소한다.

• 치료 1: 우선순위 = 8, 소요 시간 = 10
• 치료 2: 우선순위 = 5, 소요 시간 = 25
• 치료 3: 우선순위 = 3, 소요 시간 = 15

각 치료는 반드시 한 명의 의사가 담당해야 하지만, 같은 환자의 서로 다른 치료를 반드시 같은 의사가 맡을 필요는 없다. 한 명의 의사는 어느 시각에도 오직 한 명의 환자만 치료할 수 있다.

아침이 되면 모든 의사가 동시에 진료실을 열어 같은 시각에 이용 가능해진다. 그 시각에 이미 도착해 있는 환자가 있을 수 있고, 이후에 추가로 도착하는 환자도 있다. 이용 가능한 의사가 생길 때마다, 대기실에 있는 환자 중에서 다음에 받을 치료의 우선순위가 가장 높은 환자가 선택되어 그 의사에게 배정된다. 우선순위가 같은 환자가 여럿이면 도착 시각이 가장 이른 환자가 선택된다. 이용 가능한 의사가 둘 이상이면 같은 시각에 여러 환자가 동시에 다음 치료를 시작할 수 있다.

어떤 환자의 한 치료가 끝났지만 아직 남은 치료가 있다면, 그 환자는 다시 대기실로 돌아가 다음 차례를 기다린다. 한 환자의 모든 치료가 끝나면 그 환자는 응급실에서 퇴원한다.

입력에는 여러 개의 테스트 케이스가 들어 있다. 각 테스트 케이스의 첫 줄에는 두 개의 양의 정수, 즉 응급실의 의사 수와 아침에 의사들이 이용 가능해지는 시각이 주어진다. 입력의 모든 시각은 단위가 명시되지 않은 하나의 양의 정수이며 최대 1000이다.

각 테스트 케이스의 나머지 부분에는 환자 정보가 이어진다. 각 환자의 첫 줄에는 도착 시각이 주어진다. 그다음 줄들에는 그 환자가 받을 치료가 한 줄에 하나씩 주어지며, 각 치료는 우선순위와 소요 시간을 나타내는 두 개의 양의 정수로 표현된다. 한 환자의 치료들은 우선순위가 강하게 감소하는 순서로 주어진다. 어떤 두 환자도 도착 시각이 같지 않으며, 환자들은 도착 시각이 증가하는 순서로 나열된다.

두 개의 0이 적힌 줄은 한 환자 데이터의 끝을 나타내고, -1이 적힌 줄은 한 테스트 케이스의 끝을 나타내며, 다시 두 개의 0이 적힌 줄은 입력 전체의 끝을 나타낸다. 각 테스트 케이스에는 최대 500명의 의사와 500명의 환자가 있다. 모든 치료의 우선순위와 소요 시간은 최대 100이다.

각 테스트 케이스마다 먼저 Case X: 형식으로 케이스 번호(1부터 시작)를 출력한 뒤, 각 환자가 응급실에서 퇴원할 수 있는 시각을 출력한다. 각 환자는 Patient A released at clock = R 형식으로 출력하며, A는 그 환자의 도착 시각, R은 퇴원 시각이다. 환자는 퇴원 시각이 증가하는 순서로 나열하고, 퇴원 시각이 같은 환자가 여럿이면 도착 시각이 이른 순서로 출력한다.