한 번에 열리는 회의

문제

공유 회의실에서 여러 팀을 대상으로 같은 안내 회의를 한 번 진행하려 한다. 각 팀은 참석할 수 있는 가장 이른 시각을 하나씩 제출했다. 팀마다 준비에 걸리는 시간이 다르므로 제출한 시각이 서로 같을 필요는 없다. 운영자는 회의 시작 시각을 정한 뒤, 그 시각에 참석할 수 있는 팀을 모두 초대하려 한다. 각 팀이 제출한 시각을 S라고 하면, 그 팀은 S 이상 S+D 이하인 정수 시각에 시작하는 회의에 참석할 수 있다. D는 모든 팀에 공통으로 적용되는 대기 허용 시간이다. 양 끝 시각도 참석 가능한 시각에 포함된다. 예를 들어 S가 8이고 D가 3이면 시작 시각이 8, 9, 10, 11인 회의에 참석할 수 있다. 시작 시각이 7이거나 12이면 참석할 수 없다. 회의 시작 시각 T는 0 이상의 정수로 정한다. 회의실의 수용 인원에는 제한이 없으며, 팀의 크기와 회의가 끝나는 시각은 고려하지 않는다. 서로 다른 팀이 같은 시각을 제출했더라도 각각 별개의 팀으로 센다. 제출 목록은 시각순으로 정렬되어 있지 않을 수 있다. 한 팀이 참석할 수 있는 시각 중 여러 시각이 후보가 되더라도 그 팀을 중복해서 세지는 않는다. 운영자의 첫 번째 목표는 참석하는 팀의 수를 최대화하는 것이다. 최대 인원이 같은 시작 시각이 여러 개라면 그중 가장 이른 시각을 선택한다. 모든 팀을 반드시 참석시킬 필요는 없으며, 참석하지 못하는 팀에 대해 별도의 회의를 열지도 않는다. 제출한 팀이 적어도 하나 있으므로 참석 가능한 팀이 전혀 없는 시각을 답으로 선택할 일은 없다. 최대 참석 팀 수와 위 규칙으로 결정한 시작 시각을 구해야 한다.

입력

첫째 줄에 정수 N과 D가 공백으로 주어진다. 1≤N≤200,000, 0≤D≤1,000,000,000이다.
둘째 줄에 각 팀이 제출한 정수 시각 S_1, …, S_N이 공백으로 주어진다. 0≤S_i≤1,000,000,000이다.

출력

최대 참석 팀 수와, 그 수를 달성하는 가장 이른 정수 시작 시각을 공백으로 구분하여 한 줄에 출력한다.

6 3
9 2 5 3 12 5

4 5

4 0
7 2 7 2

2 2

1 10
6

1 6

출처: Devin.KR 자체 제작