VegiCat besitzt ein Unternehmen mit $n$ Mitarbeitern in $k$ nichtleeren Teams. Die Mitarbeiter wohnen entlang einer geraden Straße, die durch eine Zahlengerade dargestellt wird. VegiCat möchte zwei Treffpunkte für sie einrichten.

VegiCat teilt die Teams in zwei Mengen $A$ und $B$ auf, wobei jedes Team in genau einer Menge liegt. Er wählt für jede Menge einen Treffpunkt an einer beliebigen reellen Koordinate. Alle Mitarbeiter desselben Teams müssen zum selben Treffpunkt gehen. Jedes Team in Menge $A$ geht zum Treffpunkt für $A$, und jedes Team in Menge $B$ geht zum Treffpunkt für $B$. Jede der beiden Mengen darf leer sein.

Sei $S_A$ die Liste der Wohnorte aller Mitarbeiter in Teams aus $A$, und sei $S_B$ analog für $B$ definiert. Jeder Mitarbeiter wird einzeln gezählt, selbst wenn sich Wohnorte wiederholen.

Für eine Liste $S = (x_1, x_2, \ldots, x_m)$ von Wohnorten ist die minimale Gesamtdistanz, die diese Mitarbeiter zurücklegen müssen, um zu einem gemeinsamen Treffpunkt zu gelangen,

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

Definiere $M(S) = 0$, wenn $S$ leer ist. Hilf VegiCat, $M(S_A) + M(S_B)$ über alle Möglichkeiten, die Teams in die zwei Mengen aufzuteilen, zu minimieren.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 3 \cdot 10^5$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält zwei ganze Zahlen $n$ und $k$ ($1 \le k \le n \le 3 \cdot 10^5$), die die Anzahl der Mitarbeiter bzw. die Anzahl der Teams angeben.

Jede der nächsten $k$ Zeilen beschreibt ein Team. Die $i$-te Zeile enthält eine ganze Zahl $m_i$ ($1 \le m_i \le n$), die Anzahl der Mitarbeiter in Team $i$, gefolgt von $m_i$ ganzen Zahlen $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), ihren Wohnorten. Die Summe aller $m_i$ in einem Testfall beträgt $n$.

Wohnorte können sich wiederholen und in beliebiger Reihenfolge angegeben sein.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $3 \cdot 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine ganze Zahl aus — die minimal mögliche Gesamtreisedistanz.

Beispiele

Eingabe 1

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

Ausgabe 1

4
15

Hinweis

Im ersten Testfall schickt VegiCat Team $1$ zu einem Treffpunkt bei Position $1$ und Team $2$ zu einem Treffpunkt bei Position $8$. Die Mitarbeiter in jedem Team legen eine Gesamtdistanz von $2$ zurück, was die Antwort $4$ ergibt.

Im zweiten Testfall wählt VegiCat Treffpunkte bei $3$ und $9$. Er schickt die Teams $1$ und $2$ zum ersten Treffpunkt und Team $3$ zum zweiten. Die Mitarbeiter in den Teams $1$, $2$ und $3$ legen Gesamtdistanzen von $12$, $1$ bzw. $2$ zurück, was die Antwort $15$ ergibt.