VegiCat omistaa yrityksen, jossa on $n$ työntekijää $k$ epätyhjässä tiimissä. Työntekijät asuvat suoran tien varrella, jota esittää lukusuora. VegiCat haluaa järjestää heille kaksi kokoontumispaikkaa.

VegiCat jakaa tiimit kahteen joukkoon, $A$ ja $B$, siten että jokainen tiimi kuuluu täsmälleen yhteen joukkoon. Hän valitsee kummallekin joukolle kokoontumispaikan mistä tahansa reaalikoordinaatista. Kaikkien saman tiimin työntekijöiden on mentävä samaan kokoontumispaikkaan. Jokainen joukon $A$ tiimi menee joukon $A$ kokoontumispaikkaan, ja jokainen joukon $B$ tiimi menee joukon $B$ kokoontumispaikkaan. Kumpi tahansa joukko voi olla tyhjä.

Olkoon $S_A$ lista kaikkien joukon $A$ tiimeihin kuuluvien työntekijöiden kotien sijainneista, ja määritellään $S_B$ vastaavasti joukolle $B$. Jokainen työntekijä lasketaan erikseen, vaikka kotien sijainnit toistuisivat.

Kotien sijaintien listalle $S = (x_1, x_2, \ldots, x_m)$ pienin kokonaismatka, jonka nämä työntekijät joutuvat kulkemaan yhteen kokoontumispaikkaan, on

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

Määritellään $M(S) = 0$, kun $S$ on tyhjä. Auta VegiCatia minimoimaan $M(S_A) + M(S_B)$ yli kaikkien tapojen jakaa tiimit kahteen joukkoon.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 3 \cdot 10^5$), testitapausten lukumäärän. Seuraavaksi esitetään testitapausten kuvaukset.

Kunkin testitapauksen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $k$ ($1 \le k \le n \le 3 \cdot 10^5$), jotka ilmaisevat työntekijöiden lukumäärän ja tiimien lukumäärän.

Jokainen seuraavista $k$ rivistä kuvaa yhden tiimin. Rivi $i$ sisältää kokonaisluvun $m_i$ ($1 \le m_i \le n$), tiimin $i$ työntekijöiden lukumäärän, ja sen perässä $m_i$ kokonaislukua $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), heidän kotiensa sijainnit. Kaikkien lukujen $m_i$ summa yhdessä testitapauksessa on $n$.

Kotien sijainnit voivat toistua ja ne voidaan antaa missä tahansa järjestyksessä.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $3 \cdot 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden kokonaisluku — pienin mahdollinen kokonaismatka.

Esimerkit

Syöte 1

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

Tuloste 1

4
15

Huomautus

Ensimmäisessä testitapauksessa VegiCat lähettää tiimin $1$ kokoontumispaikkaan kohdassa $1$ ja tiimin $2$ kokoontumispaikkaan kohdassa $8$. Kummankin tiimin työntekijät kulkevat yhteensä matkan $2$, jolloin vastaus on $4$.

Toisessa testitapauksessa VegiCat valitsee kokoontumispaikat kohdista $3$ ja $9$. Hän lähettää tiimit $1$ ja $2$ ensimmäiseen kokoontumispaikkaan ja tiimin $3$ toiseen. Tiimien $1$, $2$ ja $3$ työntekijät kulkevat kokonaismatkat $12$, $1$ ja $2$, jolloin vastaus on $15$.