마라톤 훈련 신호

문제

마라톤 대회 운영진은 본 대회에 앞서 참가자들의 신호 대응 훈련을 진행한다. 참가자는 N명이며 번호는 1번부터 N번까지이다. 모든 참가자는 출발선에서 시작하고, 처음 체력은 모두 E이다. 출발선에서 결승선까지의 거리는 L이다. 훈련 중에는 운영 장치가 신호를 하나씩 보내며, 각 신호에는 신호를 받을 참가자 번호와 이동할 거리 d가 적혀 있다. 참가자가 신호를 받았을 때 현재 체력이 d 이상이면 반드시 달린다. 이때 이동한 거리에 d를 더하고 체력에서 d를 뺀다. 현재 체력이 d보다 작으면 전혀 이동하지 않고 휴식한다. 휴식하면 체력이 R만큼 증가하지만 E를 초과하지 않는다. 휴식으로 체력이 충분해지더라도 그 신호에서 다시 달리지는 않으며, 다음에 자신에게 오는 신호를 기다린다. 달린 직후 누적 이동 거리가 L 이상이 되면 해당 참가자는 완주한다. 결승선을 넘어서 이동한 거리도 그대로 두며, 완주한 참가자는 이후 자신에게 오는 모든 신호를 무시한다. 무시한 신호에서는 이동하거나 체력을 회복하지 않는다. 신호를 받지 않은 다른 참가자의 거리와 체력도 변하지 않는다. 신호는 입력에 적힌 순서대로 하나씩 처리한다. 한 신호는 정확히 한 참가자에게만 전달되므로 같은 신호에서 여러 참가자가 동시에 완주하는 일은 없다. 운영진은 가장 먼저 완주한 참가자와 그 참가자가 완주하게 된 신호의 번호를 알고 싶다. 신호 번호는 첫 번째 신호부터 1번, 2번 순서로 붙인다. 모든 신호를 처리할 때까지 아무도 완주하지 못할 수도 있다. 주어진 훈련 기록에 따라 최초 완주 결과를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, M, L, E, R이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 1,000, 1 ≤ M ≤ 40,000, 1 ≤ L ≤ 1,000,000,000, 1 ≤ E ≤ 100, 1 ≤ R ≤ E이다.
다음 M개 줄에는 신호를 받을 참가자 번호 p와 이동할 거리 d가 주어진다. p와 d는 정수이며 1 ≤ p ≤ N, 1 ≤ d ≤ E이다.

출력

완주한 참가자가 있으면 가장 먼저 완주한 참가자 번호와 완주하게 된 신호 번호를 공백으로 구분하여 한 줄에 출력한다. 아무도 완주하지 못하면 -1만 출력한다.

2 5 7 5 3
1 4
1 3
2 5
1 3
2 2

1 4

1 3 6 4 2
1 4
1 3
1 3

-1

2 3 3 5 1
2 3
2 5
1 4

2 1

출처: Devin.KR 자체 제작