Description

People who know cows understand how they form "cow neighborhoods." They observed Farmer John’s $N$ cows (numbered $1$ through $N$) grazing on a pasture modeled as a plane with $X$ and $Y$ coordinates starting from $1$, where each cow is located at a unique integer lattice point.

Two cows are neighbors if at least one of the following criteria holds:

1. Their Manhattan distance is at most $C$, i.e., $|X_i - X_j| + |Y_i - Y_j| \leq C$.
2. They share a common neighbor; that is, there exists a cow $k$ such that $i$ and $k$, and $j$ and $k$, both belong to the same group.

Given the cows’ positions and the distance $C$, determine the number of "cow neighborhoods" and the number of cows in the largest "cow neighborhood."

For example, consider the pasture below. When $C = 4$, this pasture has four neighborhoods: one large neighborhood on the left, two neighborhoods of size $1$, and a huge neighborhood on the right containing $60$ distinct cows.

.....................................*.................
....*...*..*.......................***.................
......*...........................****.................
..*....*..*.......................*...*.******.*.*.....
........................*.............***...***...*....
*..*..*...*..........................*..*...*..*...*...
.....................................*..*...*..*.......
.....................................*..*...*..*.......
...*................*..................................
.*..*............................*.*.*.*.*.*.*.*.*.*.*.
.*.....*..........................*.*.*.*.*.*.*.*.*.*.*
....*..................................................

Input Format

The first line contains two space-separated integers $N, C$.

Each of the next $N$ lines contains two space-separated integers $X_i, Y_i$, giving the coordinates of a cow.

Output Format

Output a single line with two space-separated integers: the number of "cow neighborhoods" and the size of the largest "cow neighborhood."

4 2 
1 1 
3 3 
2 2 
10 10 

2 3 

Hint

Sample Explanation #1

There are $2$ neighborhoods in the sample: one formed by the first three cows, and the other by the last cow. Therefore, the largest neighborhood size is $3$.

Constraints

For $100\%$ of the testdata, $1 \leq N \leq 10^5$, $1 \leq C \leq 10^9$, $1 \leq X_i, Y_i \leq 10^9$, and $X_i, Y_i$ are integers.

Translated by ChatGPT 5