Sieć wifi
To zadanie pochodzi z Kółka Informatycznego w Staszicu.
Grupa młodsza
Limit pamięci: 32MBPewnego słonecznego dnia dyrekcja szkoły postanowiła o konieczności rozprowadzenia sieci bezprzewodowej po całym liceum. Poinformowani o tym fakcie admini szkolnej sieci natychmiast rozpisali konkurs na projekt rozmieszczenia access pointów, tak aby w każdej klasie był zasięg.
Jesteś dzielnym mat-cosiem, chciałbyś więc taki konkurs wygrać - nagrodą główną jest bowiem zwiększenie quoty. Aby zrealizować swój cel, musisz tak zaplanować sieć, żeby w każdej klasie był najlepszy zasięg jaki jest tylko możliwy oraz żeby spełnione były pozostałe warunki. Aha... Do dyspozycji masz nie więcej niż K access pointów - jest kryzys, dyrekcja też musi oszczędzać.
Liceum, jak wszyscy wiemy, mieści się na dokładnie jednym piętrze. Wszystkie zaś klasy usytuowane są wzdłuż bardzo długiego, prostego korytarza. W szkolnym archiwum znalazłeś T planów, z odległościami każdej klasy od początku korytarza. Teraz zabierasz się do pracy...
Wejście
W pierwszej linii znajduje się liczba przypadków testowych. Pierwsza linia każdego przypadku zawiera dwie liczby całkowite n i m (1 <= m <= 100000), oznaczające kolejno liczbę access pointów, które może kupić dyrekcja, oraz liczbę klas w szkole. W kolejnych m liniach znajdują się odległości klas od początku korytarza (odległość taka nie przekracza miliona).
Wyjście
Dla każdego testu wypisz dokładnie jedną liczbę rzeczywistą - największą odległość pomiędzy klasa a access pointem znajdującym sie najbliżej tej klasy. Liczbę wypisz z dokładnością do jednej cyfrą po przecinku.
Przykład
Dla danych:1 2 3 1 3 10
poprawnym wynikiem jest:
1.0