Sparing w Programowaniu Politechnika Poznańska, 10.03.2007

Opis

Mieszkańcy Krainy Czarów zdecydowali się przeprowadzić zawody w programowaniu. Ochotnicza Komisja Sędziowska obiecała zorganizować najuczciwszy konkurs, jaki odbył się do tej pory, kiedykolwiek. Zdecydowano się na połączenie komputerów zawodników w topologię "gwiazdy" - tzn. wpięcie wszystkich komputerów do jednego przełącznika. W celu zorganizowania naprawdę uczciwych zawodów, Naczelink Komisji Sędziowskiej nakazał, aby zawodników rozsadzono w równych odległościach od przełącznika, dookoła niego.

W celu zakupu kabli sieciowych, Komisja Sędziowska podpisała z lokalnym dostawcą rozwiązań sieciowych umowę na dostarczenie określonej liczby kabli o o równej długości. Komisja Sędziowska życzy sobie również, aby kable były możliwie najdłuższe, tak aby można było posadzić zadowników najdalej jak się da od siebie.

Firmowy Kablomistrz został przydzielony do tego zadania "na ochotnika". Zna on długość każdego kabla w magazynie co do centymetra i potrafi przyciąć je z dokładności do centymetra, pod warunkiem, że wie na jak długie odcinki ma ciąć. Tym razem jednak nie wiadomo jaka ma być ta długość, dlatego Kablomistrz jest w kropce. Jednym słowem można powiedzieć, że jest "dobrze", w dwóch słowach, że jest "nie dobrze".

Tobie firma przydzieliła za zadanie asystowanie Kablomistrzowi, poprzez napisanie programu, który określi maksymalną możliwą długość odcinka kabla, która może być uzyskana z fragmenów znajdujących się w magazynie, tak aby uzyskać określoną liczbę łączy dla zawodników.

Specyfikacja wejścia

W pierwszej linii znajduje się liczba D (1 ≤ D ≤ 100) określająca liczbę testów.

Wpierwszej linii testu znajdują się dwie liczby całkowite N i K, oddzielone spacją. N (1 ≤ N ≤ 10000) jest liczbą kabli w magazynie, a K (1 ≤ K ≤ 10000) jest liczbą żądanych odcinków. Kolejne N linii zawiera pojedynczą liczbę określającą długość każdego kabla w magazynie w metrach. Każdy kabel ma przynajmniej 1 centymetr i najwyżej 100 kilometrów długości. Każda długość na wejściu jest zapisana z dokładnościa do centymetra, z dokładnie dwoma cyframi po przecinku.

Specyfikacja wyjścia

Dla każdego przypadku testowego na wyjściu wypisz maksymalną długość kabla, jaką Kablomistrz może wyciąć z kabli w magazynie, tak aby uzyskać wskazaną liczbę odcinków. Liczna musi być zapisana z dokładnością do centymetrów i mieć dokładnie dwie cyfry po przecinku

Jeżeli wycięcie określonej liczby odcinków kabla, tak, żeby każdy miał przynajmniej 1 centymetr długości, jest niemożliwe, linia na wyjściu musi zawierać liczba 0.00.

Przykład

1
4 11
8.02
7.43
4.57
5.39

2.00