VegiCat possède une entreprise comptant $n$ employés répartis en $k$ équipes non vides. Les employés vivent le long d'une route rectiligne, représentée par une droite graduée. VegiCat souhaite organiser deux points de rencontre pour eux.

VegiCat répartit les équipes en deux ensembles, $A$ et $B$, chaque équipe appartenant à exactement un ensemble. Il choisit un point de rencontre pour chaque ensemble à n'importe quelle coordonnée réelle. Tous les employés d'une même équipe doivent se rendre au même point de rencontre. Chaque équipe de l'ensemble $A$ se rend au point de rencontre de $A$, et chaque équipe de l'ensemble $B$ se rend au point de rencontre de $B$. L'un ou l'autre des ensembles peut être vide.

Soit $S_A$ la liste des positions des domiciles de tous les employés des équipes de $A$, et définissons $S_B$ de manière similaire pour $B$. Chaque employé est compté séparément, même lorsque les positions des domiciles se répètent.

Pour une liste $S = (x_1, x_2, \ldots, x_m)$ de positions de domiciles, la distance totale minimale que ces employés doivent parcourir pour rejoindre un unique point de rencontre est

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

On définit $M(S) = 0$ lorsque $S$ est vide. Aidez VegiCat à minimiser $M(S_A) + M(S_B)$ sur toutes les façons de répartir les équipes entre les deux ensembles.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 3 \cdot 10^5$), le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient deux entiers $n$ et $k$ ($1 \le k \le n \le 3 \cdot 10^5$), désignant respectivement le nombre d'employés et le nombre d'équipes.

Chacune des $k$ lignes suivantes décrit une équipe. La $i$-ème ligne contient un entier $m_i$ ($1 \le m_i \le n$), le nombre d'employés dans l'équipe $i$, suivi de $m_i$ entiers $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), les positions de leurs domiciles. La somme de tous les $m_i$ dans un cas de test vaut $n$.

Les positions des domiciles peuvent se répéter et peuvent être données dans n'importe quel ordre.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $3 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez un entier — la distance totale de déplacement minimale possible.

Exemples

Entrée 1

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

Sortie 1

4
15

Remarque

Dans le premier cas de test, VegiCat envoie l'équipe $1$ à un point de rencontre situé à la position $1$ et l'équipe $2$ à un point de rencontre situé à la position $8$. Les employés de chaque équipe parcourent une distance totale de $2$, ce qui donne la réponse $4$.

Dans le second cas de test, VegiCat choisit des points de rencontre en $3$ et $9$. Il envoie les équipes $1$ et $2$ au premier point de rencontre, et l'équipe $3$ au second. Les employés des équipes $1$, $2$ et $3$ parcourent respectivement des distances totales de $12$, $1$ et $2$, ce qui donne la réponse $15$.