VegiCat äger ett företag med $n$ anställda i $k$ icke-tomma team. De anställda bor längs en rak väg, representerad av en tallinje. VegiCat vill ordna två mötesplatser för dem.

VegiCat delar in teamen i två mängder, $A$ och $B$, där varje team ingår i exakt en mängd. Han väljer en mötesplats för varje mängd på en godtycklig reell koordinat. Alla anställda i samma team måste gå till samma mötesplats. Varje team i mängd $A$ går till mötesplatsen för $A$, och varje team i mängd $B$ går till mötesplatsen för $B$. Vardera mängden får vara tom.

Låt $S_A$ lista hempositionerna för alla anställda i teamen i $A$, och definiera $S_B$ på motsvarande sätt för $B$. Varje anställd räknas separat, även när hempositioner upprepas.

För en lista $S = (x_1, x_2, \ldots, x_m)$ av hempositioner är den minsta totala sträckan för dessa anställda att färdas till en gemensam mötesplats

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

Definiera $M(S) = 0$ när $S$ är tom. Hjälp VegiCat att minimera $M(S_A) + M(S_B)$ över alla sätt att dela in teamen i de två mängderna.

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 3 \cdot 10^5$), antalet testfall. Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller två heltal $n$ och $k$ ($1 \le k \le n \le 3 \cdot 10^5$), som anger antalet anställda respektive antalet team.

Var och en av de följande $k$ raderna beskriver ett team. Den $i$-te raden innehåller ett heltal $m_i$ ($1 \le m_i \le n$), antalet anställda i team $i$, följt av $m_i$ heltal $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), deras hempositioner. Summan av alla $m_i$ i ett testfall är $n$.

Hempositioner kan upprepas och kan ges i godtycklig ordning.

Det garanteras att summan av $n$ över alla testfall inte överstiger $3 \cdot 10^5$.

Utdata

För varje testfall, skriv ut ett heltal — den minsta möjliga totala resesträckan.

Exempel

Indata 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

Förklaring

I det första testfallet skickar VegiCat team $1$ till en mötesplats på position $1$ och team $2$ till en mötesplats på position $8$. De anställda i varje team reser en total sträcka på $2$, vilket ger svaret $4$.

I det andra testfallet väljer VegiCat mötesplatser vid $3$ och $9$. Han skickar team $1$ och $2$ till den första mötesplatsen, och team $3$ till den andra. De anställda i team $1$, $2$ och $3$ reser totala sträckor på $12$, $1$ respektive $2$, vilket ger svaret $15$.