우체국 창구 예약 즉시 판정

문제

한 우체국에는 K개의 창구가 있고, 하루 동안 N건의 방문 예약 요청이 들어온다. i번째 요청은 시작 시각 s_i와 종료 시각 e_i로 이루어지며, 해당 업무는 시각 s_i부터 e_i 직전까지 창구 하나를 사용한다. 요청이 수락되면 그 요청은 시각 s_i 이상 e_i+g 미만의 시간 동안 창구 하나를 점유한다. 여기서 g는 업무가 끝난 뒤 창구를 정리하는 데 필요한 시간이다. 요청은 시작 시각이 이른 순서로 처리하며, 시작 시각이 같으면 입력에서 앞에 있는 요청부터 처리한다. 요청을 처리하는 시점에, 시각 s_i에 창구를 점유하고 있는 수락된 요청이 K개 미만이면 그 요청을 수락하고, 그렇지 않으면 거절한다. 거절된 요청은 이후 어떤 창구도 점유하지 않는다. 점유 구간은 시작 시각을 포함하고 끝 시각을 포함하지 않는다. 따라서 어떤 수락된 요청의 e+g가 새 요청의 s와 같다면 그 창구는 이미 비어 있는 것으로 본다. 접수 담당자는 이 규칙으로 현장에서 즉시 수락 여부를 판정한다. 모든 시각과 값은 정수이며 s_i < e_i이다. 수락된 요청의 개수와, 수락된 요청의 입력 번호(1부터 시작)의 합을 구하시오.

입력

첫 줄에 세 정수 N, K, g가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ K ≤ N, 0 ≤ g ≤ 1,000,000,000) 이어서 N개의 줄에 i번째 요청의 s_i, e_i가 공백으로 구분되어 주어진다. (0 ≤ s_i < e_i ≤ 1,000,000,000)

출력

수락된 요청의 개수와 수락된 요청 번호의 합을 공백으로 구분하여 한 줄에 출력한다.

5 2 1
0 5
1 3
2 4
4 6
5 7

3 7

3 1 0
0 2
2 4
2 3

2 3

출처: Devin.KR 자체 제작