이어지는 헬스장 이용일

문제

한 헬스장은 날짜를 1부터 시작하는 정수 번호로 관리한다. 회원 한 명이 보유한 이용권은 모두 같은 길이이며, 이용권 하나는 지정된 시작일부터 K일 동안 사용할 수 있다. 시작일이 S인 이용권으로 입장할 수 있는 날짜는 S, S+1, ..., S+K-1이다. 시작일과 마지막 날을 모두 포함하며, 날짜 번호는 이용권의 유효 기간 안에서 하루씩 증가한다. 회원은 여러 장의 이용권을 가지고 있다. 서로 다른 이용권의 유효 기간이 겹쳐도 겹친 날짜를 여러 번 이용 가능한 날짜로 세지 않는다. 또한 이용권을 실제로 사용했는지는 고려하지 않는다. 적어도 한 장의 이용권이 유효한 날짜라면 모두 이용 가능한 날짜이다. 시작일이 같은 이용권이 여러 장 주어질 수 있으며, 이런 이용권도 입력에서 제거하거나 다른 날짜로 옮기지 않는다. 헬스장 안내 화면에는 이용 가능한 날짜의 총수와 연속 이용 구간의 수를 표시한다. 연속 이용 구간은 이용 가능한 날짜가 하루도 빠짐없이 이어지는 최대 범위이다. 두 이용권의 유효 기간이 겹치지 않더라도, 앞 이용권의 마지막 날 바로 다음 날에 다른 이용권이 시작하면 두 기간은 하나의 연속 이용 구간에 속한다. 반대로 그 사이에 이용할 수 없는 날짜가 하루라도 있으면 서로 다른 구간이다. 예를 들어 3일부터 5일까지와 6일부터 8일까지 이용할 수 있다면 3일부터 8일까지가 하나의 연속 이용 구간이다. 9일에 이용할 수 없고 10일에 다시 이용할 수 있다면 10일은 새로운 구간에 속한다. 주어진 모든 이용권을 함께 고려하여 안내 화면에 표시할 두 정수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 이용권 수 N과 이용권 한 장의 유효 기간 K가 공백으로 구분되어 주어진다. N은 1 이상 100,000 이하의 정수이고 K는 1 이상 1,000,000,000 이하의 정수이다.
다음 N개 줄에 각 이용권의 시작일 S가 하나씩 주어진다. S는 1 이상 1,000,000,000 이하의 정수이다. 시작일은 정렬되어 있지 않을 수 있으며 중복될 수 있다. 유효 기간의 마지막 날이 1,000,000,000을 넘어도 그 날짜까지 정상적으로 이용할 수 있다.

출력

이용 가능한 날짜의 총수와 연속 이용 구간의 수를 공백으로 구분하여 한 줄에 출력한다. 이용권이 적어도 한 장 있으므로 두 값은 모두 양수이다.

5 3
10
3
6
4
15

12 3

4 1
8
2
8
3

3 2

2 1000000000
1000000000
1

1999999999 1

출처: Devin.KR 자체 제작