VegiCat posee una empresa con $n$ empleados distribuidos en $k$ equipos no vacíos. Los empleados viven a lo largo de una carretera recta, representada por una recta numérica. VegiCat quiere organizar dos puntos de encuentro para ellos.

VegiCat divide los equipos en dos conjuntos, $A$ y $B$, de modo que cada equipo pertenezca exactamente a un conjunto. Él elige un punto de encuentro para cada conjunto en cualquier coordenada real. Todos los empleados del mismo equipo deben ir al mismo punto de encuentro. Cada equipo en el conjunto $A$ va al punto de encuentro de $A$, y cada equipo en el conjunto $B$ va al punto de encuentro de $B$. Cualquiera de los conjuntos puede estar vacío.

Sea $S_A$ la lista de las posiciones de las casas de todos los empleados de los equipos en $A$, y defínase $S_B$ de manera similar para $B$. Cada empleado se cuenta por separado, incluso cuando las posiciones de las casas se repiten.

Para una lista $S = (x_1, x_2, \ldots, x_m)$ de posiciones de casas, la distancia total mínima que deben recorrer estos empleados para ir a un único punto de encuentro es

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

Defínase $M(S) = 0$ cuando $S$ está vacía. Ayuda a VegiCat a minimizar $M(S_A) + M(S_B)$ entre todas las formas de dividir los equipos en los dos conjuntos.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 3 \cdot 10^5$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n$ y $k$ ($1 \le k \le n \le 3 \cdot 10^5$), que indican el número de empleados y el número de equipos, respectivamente.

Cada una de las siguientes $k$ líneas describe un equipo. La $i$-ésima línea contiene un entero $m_i$ ($1 \le m_i \le n$), el número de empleados en el equipo $i$, seguido de $m_i$ enteros $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), las posiciones de sus casas. La suma de todos los $m_i$ en un caso de prueba es $n$.

Las posiciones de las casas pueden repetirse y pueden darse en cualquier orden.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $3 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime un entero: la distancia total de viaje mínima posible.

Ejemplos

Entrada 1

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

Salida 1

4
15

Nota

En el primer caso de prueba, VegiCat envía al equipo $1$ a un punto de encuentro en la posición $1$ y al equipo $2$ a un punto de encuentro en la posición $8$. Los empleados de cada equipo recorren una distancia total de $2$, dando como respuesta $4$.

En el segundo caso de prueba, VegiCat elige puntos de encuentro en $3$ y $9$. Envía a los equipos $1$ y $2$ al primer punto de encuentro, y al equipo $3$ al segundo. Los empleados de los equipos $1$, $2$ y $3$ recorren distancias totales de $12$, $1$ y $2$, respectivamente, dando como respuesta $15$.