VegiCat eier et selskap med $n$ ansatte fordelt på $k$ ikke-tomme team. De ansatte bor langs en rett vei, representert ved en tallinje. VegiCat ønsker å arrangere to møtepunkter for dem.

VegiCat deler teamene inn i to mengder, $A$ og $B$, der hvert team er i nøyaktig én mengde. Han velger et møtepunkt for hver mengde på en vilkårlig reell koordinat. Alle ansatte på samme team må dra til samme møtepunkt. Hvert team i mengde $A$ drar til møtepunktet for $A$, og hvert team i mengde $B$ drar til møtepunktet for $B$. Begge mengdene kan være tomme.

La $S_A$ være listen over hjemmeposisjonene til alle ansatte på team i $A$, og definer $S_B$ tilsvarende for $B$. Hver ansatt telles separat, selv når hjemmeposisjoner gjentas.

For en liste $S = (x_1, x_2, \ldots, x_m)$ av hjemmeposisjoner er den minste totale avstanden disse ansatte må reise til ett møtepunkt

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

Definer $M(S) = 0$ når $S$ er tom. Hjelp VegiCat med å minimere $M(S_A) + M(S_B)$ over alle måter å dele teamene inn i de to mengdene på.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 3 \cdot 10^5$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder to heltall $n$ og $k$ ($1 \le k \le n \le 3 \cdot 10^5$), som angir henholdsvis antallet ansatte og antallet team.

Hver av de neste $k$ linjene beskriver ett team. Den $i$-te linjen inneholder et heltall $m_i$ ($1 \le m_i \le n$), antallet ansatte på team $i$, etterfulgt av $m_i$ heltall $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), hjemmeposisjonene deres. Summen av alle $m_i$ i et testtilfelle er $n$.

Hjemmeposisjoner kan gjentas og kan oppgis i hvilken som helst rekkefølge.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $3 \cdot 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut et heltall — den minste mulige totale reiseavstanden.

Eksempler

Inndata 1

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

Utdata 1

4
15

Forklaring

I det første testtilfellet sender VegiCat team $1$ til et møtepunkt i posisjon $1$ og team $2$ til et møtepunkt i posisjon $8$. De ansatte i hvert team reiser en total avstand på $2$, noe som gir svaret $4$.

I det andre testtilfellet velger VegiCat møtepunkter i $3$ og $9$. Han sender team $1$ og $2$ til det første møtepunktet, og team $3$ til det andre. De ansatte i team $1$, $2$ og $3$ reiser totale avstander på henholdsvis $12$, $1$ og $2$, noe som gir svaret $15$.