게임 서버의 점검 묶음

문제

한 게임 서버에는 여러 기능의 점검 요청이 접수된다. 각 요청은 점검 시작 시각 s와 종료 시각 e로 표현하며, 두 시각은 서버 기준 시계의 정수 값이다. 운영팀은 가까운 점검 요청을 하나의 묶음으로 합쳐 이용자에게 안내하려 한다. 입력된 요청은 시작 시각순으로 정리되어 있지 않다. 먼저 모든 요청을 시작 시각이 작은 순서로 정렬한다. 시작 시각이 같으면 종료 시각이 작은 요청을 먼저 둔다. 시작 시각과 종료 시각이 모두 같은 요청이 여러 개 있으면 순서는 상관없지만, 접수된 요청의 개수는 각각 따로 센다. 정렬한 첫 번째 요청으로 첫 묶음을 만든다. 묶음의 시작 시각은 처음 포함한 요청의 시작 시각이며, 종료 시각은 포함한 요청들의 종료 시각 중 최댓값이다. 이후 요청을 정렬된 순서대로 하나씩 확인한다. 현재 묶음의 종료 시각을 E라고 할 때, 다음 요청의 시작 시각이 E + K 이하이면 그 요청을 현재 묶음에 포함한다. 포함한 뒤에는 묶음의 종료 시각을 갱신한다. 다음 요청의 시작 시각이 E + K보다 크면 현재 묶음을 확정하고, 그 요청으로 새 묶음을 시작한다. 요청들이 연달아 가까이 있으면 묶음의 전체 길이가 K보다 길어져도 하나로 합쳐질 수 있다. 두 시각이 같은 요청도 유효하며, 다른 요청에 완전히 포함된 요청 역시 개수에 포함한다. 운영팀은 최종 묶음의 수와 가장 많은 요청을 포함한 묶음을 알고 싶다. 포함한 요청 수가 같은 묶음이 여러 개라면 시작 시각이 가장 이른 묶음을 고른다. 요청은 적어도 하나 주어지므로 선택할 묶음이 없는 경우는 없다. 정해진 규칙으로 모든 요청을 묶은 결과를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 20,000, 0 ≤ K ≤ 1,000,000이다.
이후 N개 줄에 각 요청의 시작 시각 s와 종료 시각 e가 공백으로 주어진다. s와 e는 정수이며 0 ≤ s ≤ e ≤ 1,000,000이다. 같은 요청이 여러 번 주어질 수 있다.

출력

첫째 줄에 최종 묶음의 수를 출력한다. 둘째 줄에 선택한 묶음의 시작 시각, 종료 시각, 포함한 요청 수를 공백으로 구분하여 출력한다. 가장 많은 요청을 포함한 묶음을 선택하며, 동점이면 시작 시각이 가장 이른 묶음을 선택한다.

6 2
20 21
1 3
8 9
5 6
30 30
21 25

3
1 9 3

4 0
10 12
0 2
12 14
2 3

2
0 3 2

3 0
7 7
7 7
7 7

1
7 7 3

출처: Devin.KR 자체 제작