Министерство национальной обороны (МНО) хочет соединить несколько северных форпостов беспроводной сетью. При создании сети должны использоваться две различные технологии связи: каждая застава будет иметь радиоприемник, а некоторые заставы дополнительно будут иметь спутниковый канал.
Любые два аванпоста со спутниковым каналом могут связываться через спутник, независимо от их местоположения. В противном случае два аванпоста могут общаться по радио, только если расстояние между ними не превышает , что зависит от мощности трансиверов. Чем выше мощность, тем выше , но стоят они больше. По соображениям покупки и обслуживания трансиверы на заставах должны быть идентичными; то есть значение должно быть одинаковым для каждой пары форпостов.
Вам следует определить наименьшее значение , необходимое для трансиверов. Между каждой парой аванпостов должен быть хотя бы один канал связи (прямой или косвенный).
Первая строка содержит количество тестов. Первая строка каждого теста содержит количество спутниковых каналов и количество аванпостов . Далее следуют строк, в которых указаны координаты каждой заставы в км (координаты — целые числа от до ).
Для каждого теста выведите минимальное , необходимое для подключения к сети. Вывод следует совершать с точностью до десятичных знаков.