Мультикилл
Зомби-апокалипсис настал! Зомби довольно легко уничтожить, однако боеприпасы в дефиците, поэтому необходимо максимально использовать взрывной потенциал. Наше самое мощное оборонительное оружие — это автоматический гранатомет, способный обнаруживать зомбированных целей на больших расстояниях. Единственное, чего не хватает, — это кода для оптимизации взрывов, чтобы поразить как можно больше целей.
Для каждой известной группы зомби вам будет предоставлен радиус поражения и координаты зомби. Программа должна определить координату для взрыва, чтобы уничтожить как можно больше зомби, и вывести максимальное количество целей, которые можно уничтожить одним выстрелом. Зомби будет уничтожен, если его расстояние от взрыва равно или меньше радиуса поражения.
Входные данные
Первая строка входных данных содержит целое число, представляющее количество тестов, C (1 ≤ C ≤ 20). Для каждого теста будет одна строка, содержащая радиус поражения в виде вещественного числа, R (0 < R ≤ 1000.0), и количество целей-зомби, N (0 ≤ N ≤ 25), за которыми следуют N строк, каждая из которых содержит пару декартовых координат X Y (-10^6 ≤ X, Y ≤ 10^6), указывающих положение каждого зомби. Единицы измерения радиуса поражения и координат — метры.
C
R N
X0 Y0
...
XN-1 YN-1
Выходные данные
Вывод должен содержать одну строку для каждого теста с количеством целей, которые могут быть уничтожены одним взрывом. Результаты для каждого теста должны быть выведены на отдельной строке.
K0
...
KC-1