Problem Description

There are $n$ bombs $[1 \ldots n]$ on a plane. The explosion range of each bomb is $|x-x_i|+|y-y_i| \leqslant R$. If a bomb explodes, it will ignite all bombs within its range.

Find the minimum number of bombs that must be ignited at the beginning so that all bombs will eventually explode.

Input Format

The first line contains two integers $n,r$.

The next $n$ lines each contain two integers $x_i,y_i$, the coordinates of a bomb.

Output Format

Output one line with an integer $k$, the minimum number of bombs to ignite.

3 2
0 0
0 2
3 2

2

Hint

For $30\%$ of the testdata, $1 \leqslant n \leqslant 1000$.

For $100\%$ of the testdata, $1 \leqslant n \leqslant 100000 \,,\, 0 \leqslant r \leqslant 10^9 \,,\, 0 \leqslant x_i,y_i \leqslant 10^9$.

Translated by ChatGPT 5