VegiCat memiliki sebuah perusahaan dengan $n$ karyawan yang terbagi dalam $k$ tim tak kosong. Para karyawan tinggal di sepanjang jalan lurus, yang direpresentasikan oleh sebuah garis bilangan. VegiCat ingin mengatur dua titik pertemuan untuk mereka.

VegiCat membagi tim-tim tersebut ke dalam dua himpunan, $A$ dan $B$, dengan setiap tim berada di tepat satu himpunan. Ia memilih satu titik pertemuan untuk setiap himpunan pada koordinat riil mana pun. Semua karyawan dalam tim yang sama harus pergi ke titik pertemuan yang sama. Setiap tim di himpunan $A$ pergi ke titik pertemuan untuk $A$, dan setiap tim di himpunan $B$ pergi ke titik pertemuan untuk $B$. Salah satu himpunan boleh kosong.

Misalkan $S_A$ memuat daftar posisi rumah dari semua karyawan pada tim-tim di $A$, dan definisikan $S_B$ secara serupa untuk $B$. Setiap karyawan dihitung secara terpisah, meskipun posisi rumah berulang.

Untuk suatu daftar posisi rumah $S = (x_1, x_2, \ldots, x_m)$, total jarak minimum yang harus ditempuh para karyawan ini menuju satu titik pertemuan adalah

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

Definisikan $M(S) = 0$ ketika $S$ kosong. Bantulah VegiCat meminimalkan $M(S_A) + M(S_B)$ di antara semua cara membagi tim-tim tersebut ke dalam dua himpunan.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 3 \cdot 10^5$), banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama dari setiap kasus uji berisi dua bilangan bulat $n$ dan $k$ ($1 \le k \le n \le 3 \cdot 10^5$), masing-masing menyatakan banyaknya karyawan dan banyaknya tim.

Masing-masing dari $k$ baris berikutnya mendeskripsikan satu tim. Baris ke-$i$ berisi sebuah bilangan bulat $m_i$ ($1 \le m_i \le n$), banyaknya karyawan pada tim $i$, diikuti oleh $m_i$ bilangan bulat $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), posisi rumah mereka. Jumlah dari semua $m_i$ dalam satu kasus uji adalah $n$.

Posisi rumah dapat berulang dan dapat diberikan dalam urutan apa pun.

Dijamin bahwa jumlah nilai $n$ di seluruh kasus uji tidak melebihi $3 \cdot 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat — total jarak perjalanan minimum yang mungkin.

Contoh

Masukan 1

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

Keluaran 1

4
15

Catatan

Pada kasus uji pertama, VegiCat mengirim tim $1$ ke titik pertemuan di posisi $1$ dan tim $2$ ke titik pertemuan di posisi $8$. Para karyawan di setiap tim menempuh total jarak sebesar $2$, sehingga menghasilkan jawaban $4$.

Pada kasus uji kedua, VegiCat memilih titik pertemuan di $3$ dan $9$. Ia mengirim tim $1$ dan $2$ ke titik pertemuan pertama, serta tim $3$ ke titik pertemuan kedua. Para karyawan di tim $1$, $2$, dan $3$ masing-masing menempuh total jarak sebesar $12$, $1$, dan $2$, sehingga menghasilkan jawaban $15$.