VegiCat á fyrirtæki með $n$ starfsmönnum í $k$ ótómum teymum. Starfsmennirnir búa við beinan veg sem táknaður er með talnalínu. VegiCat vill skipuleggja tvo fundarstaði fyrir þá.

VegiCat skiptir teymunum í tvö mengi, $A$ og $B$, þannig að hvert teymi sé í nákvæmlega einu mengi. Hann velur fundarstað fyrir hvort mengi í hvaða rauntöluhnitum sem er. Allir starfsmenn í sama teymi verða að fara á sama fundarstað. Hvert teymi í mengi $A$ fer á fundarstaðinn fyrir $A$, og hvert teymi í mengi $B$ fer á fundarstaðinn fyrir $B$. Hvort mengið sem er má vera tómt.

Látum $S_A$ vera lista yfir staðsetningar heimila allra starfsmanna í teymum í $A$, og skilgreinum $S_B$ á svipaðan hátt fyrir $B$. Hver starfsmaður er talinn sérstaklega, jafnvel þótt staðsetningar heimila endurtaki sig.

Fyrir lista $S = (x_1, x_2, \ldots, x_m)$ af staðsetningum heimila er minnsta heildarvegalengd sem þessir starfsmenn þurfa að ferðast á einn fundarstað

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

Skilgreinum $M(S) = 0$ þegar $S$ er tómt. Hjálpaðu VegiCat að lágmarka $M(S_A) + M(S_B)$ yfir allar leiðir til að skipta teymunum í mengin tvö.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 3 \cdot 10^5$), fjölda prófunartilvika. Lýsing á prófunartilvikunum fylgir.

Fyrsta línan í hverju prófunartilviki inniheldur tvær heiltölur $n$ og $k$ ($1 \le k \le n \le 3 \cdot 10^5$), sem tákna fjölda starfsmanna og fjölda teyma, í sömu röð.

Hver af næstu $k$ línum lýsir einu teymi. Lína $i$ inniheldur heiltölu $m_i$ ($1 \le m_i \le n$), fjölda starfsmanna í teymi $i$, og á eftir henni fylgja $m_i$ heiltölur $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), staðsetningar heimila þeirra. Summa allra $m_i$ í prófunartilviki er $n$.

Staðsetningar heimila geta endurtekið sig og geta verið gefnar í hvaða röð sem er.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $3 \cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta út heiltölu — minnstu mögulegu heildarferðavegalengd.

Dæmi

Inntak 1

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

Úttak 1

4
15

Athugasemd

Í fyrsta prófunartilvikinu sendir VegiCat teymi $1$ á fundarstað í stöðu $1$ og teymi $2$ á fundarstað í stöðu $8$. Starfsmennirnir í hvoru teymi ferðast heildarvegalengdina $2$, sem gefur svarið $4$.

Í öðru prófunartilvikinu velur VegiCat fundarstaði í $3$ og $9$. Hann sendir teymi $1$ og $2$ á fyrri fundarstaðinn, og teymi $3$ á þann seinni. Starfsmennirnir í teymum $1$, $2$ og $3$ ferðast heildarvegalengdirnar $12$, $1$ og $2$, í sömu röð, sem gefur svarið $15$.