플러드 필 (Flood Fill)

평면 위에 $M$개의 점이 놓여 있다. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 택시 거리(taxicab distance) 는 $|x_1 - x_2| + |y_1 - y_2|$로 정의된다.

두 점의 택시 거리가 $D$ 이하이면 두 점은 서로 직접 연결되어 있다고 한다. 직접 연결을 여러 번 거쳐 서로 도달할 수 있는 점들의 모임을 하나의 섬(island) 이라고 부른다. 즉, 섬은 '직접 연결' 관계로 만들어지는 연결 요소(connected component)이다.

주어진 점들에 대해 섬의 개수와, 가장 큰 섬에 속한 점의 개수(가장 큰 섬의 크기)를 구하여라.

$D = 1$이면 같은 칸이거나 상하좌우로 한 칸 떨어진 점만 연결되는, 잘 알려진 Flood Fill 문제와 같다. 이 문제는 그 기준 거리를 임의의 $D$로 일반화한 것이다.

첫째 줄에 점의 개수 $M$과 기준 거리 $D$가 주어진다. ($1 \le M \le 100000$, $1 \le D \le 10^9$)

이어지는 $M$개의 줄에 각 점의 좌표 $X_i$와 $Y_i$가 주어진다. ($1 \le X_i, Y_i \le 10^9$)

같은 좌표를 가진 점이 여러 번 주어질 수 있으며, 이 경우 두 점의 택시 거리는 $0$이므로 항상 같은 섬에 속한다.

섬의 개수와 가장 큰 섬의 크기를 공백으로 구분하여 한 줄에 출력한다.

좌표 범위가 매우 크므로 모든 점의 쌍을 직접 비교하면 느릴 수 있다. $u = x + y$, $v = x - y$로 좌표를 바꾸면 택시 거리가 체비쇼프 거리 $\max(|u_1 - u_2|,\ |v_1 - v_2|)$와 같아진다. 그러면 두 점이 직접 연결될 조건은 $|u_1 - u_2| \le D$ 이면서 $|v_1 - v_2| \le D$, 즉 변환된 좌표에서 한 변의 길이가 $D$인 정사각형 안에 함께 들어가는지로 단순해진다.