Hide

Problem F
Pesky Mosquitoes

Mosquitoes are relentless this time of year! They have absolutely ruined your attempt at a picnic and it is time to take your revenge. Unfortunately, you are not well equipped to ward off these pests. All you have got at your disposal is an empty bowl that previously held potato salad. As you glance down at the picnic table, you see a number of mosquitoes waiting idly for you to let your guard down. This is your chance to fight back.

Your task is to determine the maximum number of mosquitoes that can be trapped by quickly bringing down the inverted bowl onto the table. You will be provided with the diameter of the bowl and the exact location of each mosquito on the table. In this exercise you can assume that the mosquitoes are incredibly small and can simply be modeled as a point. A mosquito that lies exactly under the edge of the bowl is considered trapped.

Input

The first number in the input will be an integer $1 \leq n \leq 100$ that denotes the number of mosquito-trapping scenarios that follow. A blank line comes at the beginning of each scenario. Then follows a line containing an integer $1 \leq m \leq 32$ (the number of mosquitoes) and a real number $0 < d \leq 200$ (the diameter of the bowl). Each of the following $m$ lines will specify the location of a mosquito in the form of real coordinates $-100 \leq x \leq 100$ and $-100 \leq y \leq 100$.

Output

For each scenario, you are to print the maximum number of mosquitoes that can be caught under the bowl in that scenario. You may assume that the answer would not change if the diameter of the bowl is increased by at most $10^{-5}$.

Sample Input 1 Sample Output 1
2

4 1.5
1.0 3.75
3.0 1.0
1.0 2.25
1.5 3.0

8 3.0
-1.0 3.0
-1.0 2.0
-2.0 1.0
0.0 1.0
1.0 0.0
1.0 -1.0
2.0 -2.0
3.0 -1.0
3
4

Please log in to submit a solution to this problem

Log in