AlgoLiga 2018

Stan Kowalsky od dawna pracuje jako taksówkarz na Manhattanie i "wozi" swoich pasażerów pomiędzy różnymi miejscami w przestrzeni k-wymiarowej. Lot z jednego punktu do drugiego składa się z pojedynczych skoków teleportacyjnych, takich, w których położenie taksówki zmienia się tylko w jednym wymiarze. Zakładając na przykład, że Stan porusza się w przestrzeni pięciowymiarowej, to aby przenieść się z punktu o współrzędnych (3, 1, 8, 1, 2) do punktu (3, 7, 8, 1, 0), musi wykonać dwa skoki. Pierwszy z nich musi nastąpić do punktu (3, 7, 8, 1, 2) albo do punktu (3, 1, 8, 1, 0). Niezależnie od tego, którą trasę wybierze, odległość, którą pokona wynosi 8 jednostek.

Stan każdego dnia rozpoczyna pracę w bazie, która znajduje się w punkcie o wszystkich współrzędnych zerowych. Następnie przewozi swoich pasażerów latając po kolei do punktów, o określonych współrzędnych. Na koniec wraca do bazy.

Taksówkarz po zakończonej pracy chciałby wiedzieć, jaki najdłuższy lot odbył w danym dniu oraz ile pojedynczych skoków musiał wykonać.

Wejście

W pierwszej linii liczba przypadków testowych (dni) t (t ≤ 100).

W pierwszej linii pojedynczego testu dwie liczby całkowite: liczba wymiarów przestrzeni k (1 ≤ k ≤ 1000) oraz liczba punktów, do których kolejno latał taksówkarz n (1 ≤ n ≤ 100).
W każdej z kolejnych n linii po k liczb całkowitych x_i dla i=1..k (-10⁹ ≤ x_i ≤ 10⁹).

Wyjście

Dla każdego testu w osobnej linii dwie liczby całkowite. Najpierw największa odległość pokonana w czasie jednego lotu (uwzględniając lot z bazy do pierwszego punktu i lot z ostatniego punktu do bazy). Następnie liczba pojedynczych skoków teleportacyjnych wykonanych w danym dniu.

Przykład

Wejście:
1
5 2
3 1 8 1 2
3 7 8 1 0

Wyjście:
19 11