VegiCat jest właścicielem firmy zatrudniającej $n$ pracowników podzielonych na $k$ niepustych zespołów. Pracownicy mieszkają wzdłuż prostej drogi, reprezentowanej przez oś liczbową. VegiCat chce zorganizować dla nich dwa punkty spotkań.

VegiCat dzieli zespoły na dwa zbiory, $A$ i $B$, przy czym każdy zespół trafia dokładnie do jednego zbioru. Dla każdego zbioru wybiera punkt spotkania o dowolnej współrzędnej rzeczywistej. Wszyscy pracownicy z tego samego zespołu muszą udać się do tego samego punktu spotkań. Każdy zespół ze zbioru $A$ udaje się do punktu spotkań dla $A$, a każdy zespół ze zbioru $B$ udaje się do punktu spotkań dla $B$. Którykolwiek ze zbiorów może być pusty.

Niech $S_A$ będzie listą pozycji domów wszystkich pracowników z zespołów należących do $A$, a $S_B$ niech będzie zdefiniowane analogicznie dla $B$. Każdy pracownik jest liczony osobno, nawet jeśli pozycje domów się powtarzają.

Dla listy $S = (x_1, x_2, \ldots, x_m)$ pozycji domów minimalna łączna odległość, jaką ci pracownicy muszą pokonać, aby dotrzeć do jednego punktu spotkań, wynosi

$$M(S) = \min_{p \in \mathbb{R}} \sum_{j=1}^{m} |x_j - p|.$$

Przyjmujemy $M(S) = 0$, gdy lista $S$ jest pusta. Pomóż VegiCatowi zminimalizować wartość $M(S_A) + M(S_B)$ po wszystkich sposobach podziału zespołów na dwa zbiory.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 3 \cdot 10^5$), oznaczającą liczbę przypadków testowych. Poniżej znajdują się opisy poszczególnych przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $k$ ($1 \le k \le n \le 3 \cdot 10^5$), oznaczające odpowiednio liczbę pracowników oraz liczbę zespołów.

Każdy z kolejnych $k$ wierszy opisuje jeden zespół. Wiersz o numerze $i$ zawiera liczbę całkowitą $m_i$ ($1 \le m_i \le n$), oznaczającą liczbę pracowników w zespole $i$, po której następuje $m_i$ liczb całkowitych $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), oznaczających pozycje ich domów. Suma wszystkich $m_i$ w jednym przypadku testowym wynosi $n$.

Pozycje domów mogą się powtarzać i mogą być podane w dowolnej kolejności.

Zagwarantowane jest, że suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $3 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — minimalną możliwą łączną odległość podróży.

Przykład

Wejście 1

2
4 2
2 1 3
2 8 10
8 3
3 4 12 1
2 3 2
3 9 8 10

Wyjście 1

4
15

Uwagi

W pierwszym przypadku testowym VegiCat wysyła zespół $1$ do punktu spotkań na pozycji $1$, a zespół $2$ do punktu spotkań na pozycji $8$. Pracownicy w każdym zespole pokonują łączną odległość równą $2$, co daje odpowiedź $4$.

W drugim przypadku testowym VegiCat wybiera punkty spotkań na pozycjach $3$ oraz $9$. Wysyła zespoły $1$ i $2$ do pierwszego punktu spotkań, a zespół $3$ do drugiego. Pracownicy w zespołach $1$, $2$ oraz $3$ pokonują łączne odległości odpowiednio $12$, $1$ oraz $2$, co daje odpowiedź $15$.