Hide

Problem B
Artillery Strike

Alice is playing a wargame, and she controls an artillery unit. She has received a report from the artillery spotter that details the precise locations of the enemies. The artillery unit that Alice controls can fire a shot that will defeat all enemies within a radius $R$ of where the artillery shell lands. What is the maximum number of enemies that Alice can defeat in her next shot?

Notes

A potentially helpful formula is the radius, $Rc$, of the circle whose perimeter intersects all three vertices of a triangle with side lengths $a, b, c$ and area $A$ is $Rc=\frac{abc}{4A}$

Input

The first line contains 2 integers, $1 \leq N \leq 200$, the number of enemies, and $1 \leq R \leq 300$, the radius of the artillery shot. The next $N$ lines each contain 2 integers, $-100 \leq x_i, y_i \leq 100$, the location of the $i-th$ enemy.

Output

Output a single number: the maximum possible number of enemies that the artillery unit can defeat in the next shot.

Sample Input 1 Sample Output 1
3 10
0 0
0 20
0 -10
2
Sample Input 2 Sample Output 2
3 4
0 0
0 20
0 -10
1
Sample Input 3 Sample Output 3
4 17
0 0
3 29
27 11
29 11
3

Please log in to submit a solution to this problem

Log in