Мультивбивство
Зомбі-апокаліпсис вже настав! Зомбі легко знищити, але боєприпаси в дефіциті, тому ми повинні максимально ефективно використовувати наші ресурси. Нашою найпотужнішою зброєю є автоматичний гранатомет, здатний виявляти зомбі на великих відстанях. Єдине, чого бракує, — це код для оптимізації вибухів, щоб уразити якомога більше цілей одночасно.
Для кожної відомої групи зомбі вам буде надано радіус ураження та координати зомбі. Програма повинна визначити оптимальну точку для вибуху, щоб знищити максимальну кількість зомбі, і вивести максимальну кількість цілей, які можна вразити одним пострілом. Зомбі буде знищено, якщо його відстань до вибуху не перевищує радіус ураження.
Вхідні дані
Перший рядок введення містить ціле число, яке вказує на кількість тестових випадків, 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