Opis

Pan Alib Rekoons jest znanym na świecie i bardzo cenionym producentem wyrobów związanych z grą w bilard. W swojej ofercie ma wszystkie przeznaczone do tej gry produkty, od stołów bilardowych do przeróżnych bardzo dziwnych gadżetów. Jednym z powodów, dla których wyroby Aliba Rekoonsa są tak bardzo cenione na świecie jest to, że wszystkie produkty wykonywane są ręcznie z najlepszych dostępnych materiałów. Drugim niemniej ważnym powodem jest to, że Alib Rekoons nie boi się nowych wyzwań i nie ma dla niego rzeczy nie do wykonania. Przykładem na to może być najnowsze bardzo nietypowe zlecenie. Jeden z klientów zamówił stół okrągły, w którym pewna liczba łuz rozmieszczona jest dookoła stołu w równych, podanych w zamówieniu, odstępach. Łuzy o średnicy nieco większej od średnicy bili, mają być wykonane z drogiego przeźroczystego tworzywa i mają pomieścić wszystkie bile, które do nich wpadną między początkiem a końcem gry. Razem ze stołem zamówiono partię bil w różnych kolorach. W zamówieniu podano dokładnie ile ma być bil w każdym kolorze.

Znane są również zasady gry, która będzie rozgrywana na tego typu stole. Gra jest jednoosobowa. Każda partia składa się z kilku rund. Każda runda polega na wbijaniu do kolejnych leżących na obwodzie stołu łuz po jednej bili, zgodnie z kierunkiem ruchu wskazówek zegara. Nie można jednak złamać nadrzędnej zasady gry, która mówi, że w danej rundzie nie można wbić dwóch bil tego samego koloru, ani nie można wbić dwóch bil do tej samej łuzy. Gdy w danej rundzie nie jest już możliwe dalsze wbijanie bil do pozostałych łuz, bieżąca runda kończy się, i zaczyna się nowa. Każda runda zawsze zaczyna się od łuzy numer jeden.

Zamówiony stół będzie wykorzystany w turnieju, w którym gracze mają za zadanie wbić wszystkie bile tak, aby nie naruszyć reguł gry. Zwycięzcą turnieju zostanie ten, który umieści jak najmniej bil w pierwszej łuzie, a jeśli będzie kilku takich graczy, to w ten sam sposób będzie decydować liczba bil w drugiej łuzie. Jeśli i to nie da rozstrzygnięcia — będzie brana pod uwagę następna łuza, itd. aż do ostatniej łuzy. Jeśli i to nie da rozstrzygnięcia to zadecyduje czas, w jakim gracze wbili wszystkie swoje bile. Jednak, aby zaoszczędzić nieco czasu w trakcie turnieju, organizatorzy zażyczyli sobie, żeby stoły były tak skonstruowane, aby łatwo było wychwycić tych graczy, którzy nie mają szans na zwycięstwo, ponieważ nie są w stanie osiągnąć najlepszego rozmieszczenia bil. Z tego wynika, że rozmiary łuz mają być tak dobrane, aby pomieściły tylko tyle bil ile potrzeba, aby uzyskać wynik nie do pobicia. Zatem każda łuza ma mieć minimalny, ograniczony regułami gry, rozmiar, przy założeniu, że łuzy o mniejszych numerach mają już poprawnie określony swój minimalny rozmiar.

Zadanie

Dla podanej w zamówieniu liczby łuz, kolorów i bil każdego koloru, podaj ile bil musi pomieścić pierwsza łuza oraz ile mniej bil musi pomieścić ostatnia łuza, przy założeniu optymalnej gry.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę różnych zamówień, jakie otrzymał pan Alib Rekoons na tego typu stół. Opis każdego zamówienia składa się z trzech linii. Pierwsza linia zawiera liczbę całkowitą N (1 ≤ N ≤ 10000), oznaczającą liczbę łuz. Druga linia zawiera liczbę całkowitą K (1 ≤ K ≤ 100000), oznaczającą liczbę kolorów w jakich mają być wykonane bile. Ostatnia linia zawiera K liczb całkowitych dodatnich, określających ile ma być bil poszczególnych kolorów. Ich suma nie przekracza 1000000000.

Specyfikacja wyjścia

Dla każdego zamówienia należy wypisać, w osobnej linii, dwie liczby całkowite. Pierwsza określa rozmiar łuzy numer jeden, czyli liczbę bil, które powinny się w niej zmieścić. Druga określa o ile bil będzie mniejszy rozmiar łuzy numer N w stosunku do rozmiaru pierwszej łuzy.

Przykład

3
3
6
2 2 2 3 2 2
6
4
1 15 3 7
4
4
8 4 2 1

5 1
15 15
8 7