1678번 - 기차

사무실에서 가까스로 도망친(장애물이 계단을 막고 있는 입력이 주어졌다) 이 사장은 기차를 이용하여 멀리 도망치기로 결심하였다. 도망을 치는 도중에 한 기차를 오래 타고 있는 것은 위험했기 때문에, 이 사장은 같은 기차를 타고 두 역 이상을 이동하지 않기로 하였다. 기차의 종류가 같더라도 출발 시간이 다르면 같은 기차가 아니다.

모든 기차는 0번 역에서 각 기차의 고유 출발시간에 매 시간마다 계속 출발한다. 이 사장은 0번 역에서 한 기차를 타고 1번 역에서 내린다. 그리고 1번 역에서 기차를 기다리다 가장 먼저 오는 기차를 타고 2번 역으로 이동한다. 그리고 2번 역에서 가장 먼저 도착한 기차를 타고 3번 역으로 이동하며, 이를 N번 역에 도착할 때까지 반복한다.

이와 같이 N번 역으로 이동했을 때, 가장 마지막에 탄 기차의 번호를 출력하는 프로그램을 작성하시오.

첫째 줄에 기차의 종류 개수 T(<30), 이 사장이 출발하는 시간(분 단위로) M(<60), N(<1,000,000,000)이 주어진다. 다음 줄에는 각 기차 종류별로 기차의 번호(길이 10을 넘지 않는 문자열)과 그 기차가 0번 역에서 출발하는 시간을 분 단위(<60)로 입력한다. 각 줄의 끝에는 -1로 주어진다. 같은 시간에 출발하는 기차는 없다고 가정해도 좋다.

첫째 줄에 기차의 번호를 출력한다