시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 19 8 5 45.455%

문제

재현이는 얼마 전, 그래프 탐색에 대해서 배웠다. 강의를 맡은 지학이는 그래프 탐색을 통해서 풀 수 있는 대표적인 문제인 Flood Fill에 대해서 알려주었다.

  • N * N 격자에 M개의 점이 있을 때, 상하좌우에 붙어있는 인접한 셀을 연결되어 있다고 하자, 연결되어 있는 점들의 집합을 “섬” 이라고 부르면, 섬의 개수와, 가장 큰 섬의 크기는 얼마인가?

이 문제를 푸는 법은 여러 방법이 있지만, 재현이는 깊이 우선 탐색으로 문제를 풀었다. 재현이는 점들을 정점이라 생각하고, 연결되어 있는 점들 사이에 간선을 이으면, 그래프의 컴포넌트의 개수와, 가장 큰 컴포넌트의 크기를 묻는 문제로 변환됨을 알아냈다. 재현이는 이를 깊이 우선 탐색으로 구한 후 지학이에게 자랑하였다.

지학이는 재현이가 이 문제를 푼 것을 본 후 감탄하여, 문제를 조금 더 어렵게 해서 주었다.

  • N은 무조건 1,000,000,000이다. 고로 격자의 크기는 1,000,000,000 * 1,000,000,000 크기이다.
  • (x1, y1) 점과 (x2, y2) 점의 “택시 거리” 는 |x2 - x1| + |y2 - y1| 으로 정의된다. 이 정의대로라면 상하좌우에 인접한 셀은 택시 거리가 1 이하인 셀의 쌍이었다는 것을 알 수 있다. 지학이는 “붙어있다” 의 정의를 바꿨다
  • 택시 거리가 1 이하가 아니라, 택시 거리가 D 이하이면 붙어 있는 것이다.

이 문제는 갓 그래프 탐색을 배운 재현이에게 너무 어려운 문제였고, 재현이는 여러분들에게 도움을 요청했다. 재현이를 도와주자!

입력

첫번째 줄에 M과 D가 주어진다. (1 <= M <= 100,000, 1 <= D <= 1,000,000,000)

이후 M개의 줄에 점의 좌표 Xi, Yi가 주어진다. (1 <= Xi, Yi <= 1,000,000,000)

출력

지학이가 어렵게 바꾼 문제의 정의대로, 섬의 개수와 가장 큰 섬의 크기를 출력하라.

예제 입력

4 2
1 1
3 3
2 2
10 10

예제 출력

2 3

힌트

(1,1) - (3,3) - (2,2) 셀은 연결되었으며, (10, 10) 셀은 혼자이다. 섬의 개수는 2개이고, 가장 큰 섬은 크기가 3이다.