정비 주기가 있는 생산 라인

문제

어느 공장에 1번부터 K번까지 번호가 붙은 기계 K대가 있다. 작업 N개가 순서대로 도착한다. i번째 작업은 (i-1)번째 작업이 도착하고 g_i분 뒤에 도착하며, 첫 번째 작업은 시각 0에서 g_1분 뒤에 도착한다. 즉 i번째 작업의 도착 시각은 g_1+…+g_i이다. i번째 작업의 가공 시간은 p_i분이다. 작업은 반드시 도착 순서대로 시작한다. 어떤 작업도 앞선 작업의 시작 시각보다 먼저 시작할 수 없으며, 같은 시각에 시작하는 것은 허용된다. 각 작업은 다음 규칙으로 기계에 배정된다. 먼저 시작 시각 s를 정한다. s는 그 작업의 도착 시각 이상이고, 앞선 작업의 시작 시각 이상이며, 그 시각에 사용 가능한 기계가 하나 이상 있는 가장 이른 시각이다. 그다음 시각 s에 사용 가능한 기계 중 번호가 가장 작은 기계에 작업을 배정한다. 모든 기계는 시각 0부터 사용 가능하다. 기계는 작업을 마치면 곧바로 쉬어야 하며 쉬는 동안에는 사용할 수 없다. 작업이 시각 s에 시작해 s+p에 끝나면, 기계는 보통 c분을 쉬고 s+p+c부터 다시 사용 가능하다. 단, 그 기계가 누적 L번째, 2L번째, 3L번째, … 작업을 마친 경우에는 정비를 위해 c분 대신 D분을 쉰다. 쉬는 시간이 끝나는 시각부터 그 기계는 사용 가능하며 그 시각도 포함한다. 각 작업이 배정된 기계 번호와 시작 시각을 입력 순서대로 출력하라.

입력

첫 줄에 다섯 정수 N K L c D가 공백으로 주어진다. 이어지는 N개의 줄에 i번째 줄마다 두 정수 g_i p_i가 주어진다. 1 ≤ N ≤ 200000, 1 ≤ K ≤ 200000, 1 ≤ L ≤ 1000000000, 0 ≤ c, D ≤ 1000000000, 0 ≤ g_i ≤ 1000000000, 1 ≤ p_i ≤ 1000000000이다. 모든 값은 정수이다.

출력

N개의 줄에 i번째 작업이 배정된 기계 번호와 시작 시각을 공백으로 구분해 출력한다.

4 2 2 1 5
0 3
1 2
1 2
1 1

1 0
2 1
1 4
2 4

1 1 1 0 0
5 3

1 5

3 1 2 2 10
0 1
0 1
0 1

1 0
1 3
1 14

출처: Devin.KR 자체 제작