Description

There are $n$ key points on the plane, each with integer coordinates in $[1,10^5]$.

It is guaranteed that these key points are four-connected, and that the plane becomes eight-connected after removing these key points.

Let $dis(i,j)$ denote the shortest path length from the $i$-th key point to the $j$-th key point, where a valid path is defined as follows:

A path is a sequence of point pairs $(x_1,y_1),(x_2,y_2),\dots,(x_k,y_k)$, where the Manhattan distance between each pair of adjacent points is $1$, that is, $\forall i\in[1,n), |x_i-x_{i+1}|+|y_i-y_{i+1}|=1$, and every point in the sequence is a key point.

The length of this path is defined as $k-1$, and the shortest path between two points is the shortest among all valid paths.

Given $n$ and $k$, find how many pairs $(i,j)$ satisfy $dis(i,j)=k$.

Input Format

The first line contains two integers, $n$ and $k$, representing the number of key points and the parameter $k$.

The next $n$ lines each contain two integers, where the $i$-th line gives the coordinates $(x_i, y_i)$ of the $i$-th key point.

It is guaranteed that the given points are distinct and satisfy the properties described above.

Output Format

Output a single integer representing the answer.

5 2
1 3
1 4
2 4
2 5
2 6

3

Hint

Data Range

This problem uses bundled tests.

• For $100\%$ of the data, it is guaranteed that $1\le n,k,x_i,y_i\le 10^5$.

Translated by ChatGPT 4.1