User's AC Ratio

96.6% (28/29)

Submission's AC Ratio

75.0% (33/44)

Description

Alan and Brian want to live in Fantasy City.
They need to choose two house to live.
Fantasy City can be represent as an cartesian coordinate plane.
And all of houses are located on lattice point, in other words, both of x and y coordinates are integers.

But they want to contact to each other with radio.
And the radio's effective range is $d$.
So they want to choose two houses and their distance is less than or equal to $d$.
Please help them to calculate how many choices they can choose.

For example:

In this picture, there are $5$ points which are houses.
$(0,0),(3,2),(-1,-3),(3,0),(-2,1)$
Assume that the effective range $d=3$.
Then they have $3$ choices to choose.
$distance(A,B)=\sqrt{(3-0)^ 2+(0-0)^ 2}=\sqrt{9}\leq3$
$distance(B,D)=\sqrt{(3-3)^ 2+(2-0)^ 2}=\sqrt{4}\leq3$
$distance(A,E)=\sqrt{(0+2)^ 2+(1-0)^ 2}=\sqrt{5}\leq3$

Any two different houses are on different point.

Input Format

First line contains two integers $N$ and $d$, which represent the total number of houses and the effective range of radio.
Following $N$ lines, each line contains two intergers $x$ and $y$ seperated by a space, which are x-coordinate and y-coordinate respectively.

  • $2\leq N\leq 1000$
  • $|x|, |y| \leq 10^ 4$
  • $0\leq d\leq28285$

Output Format

One line contains an integer - the number of choices.

Sample Input 1

5 3
0 0
3 2
-1 -3
3 0
-2 1

Sample Output 1

3

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~7 All of houses are on x-axis 5
2 0~15 No specified restriction 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2
1 1000 65536 65536 1 2
2 1000 65536 65536 1 2
3 1000 65536 65536 1 2
4 1000 65536 65536 1 2
5 1000 65536 65536 1 2
6 1000 65536 65536 1 2
7 1000 65536 65536 1 2
8 1000 65536 65536 2
9 1000 65536 65536 2
10 1000 65536 65536 2
11 1000 65536 65536 2
12 1000 65536 65536 2
13 1000 65536 65536 2
14 1000 65536 65536 2
15 1000 65536 65536 2