VegiCat sở hữu một công ty có $n$ nhân viên trong $k$ đội khác rỗng. Các nhân viên sống dọc theo một con đường thẳng, được biểu diễn bằng một trục số. VegiCat muốn sắp xếp hai điểm tập trung cho họ.

VegiCat chia các đội thành hai tập hợp $A$ và $B$, mỗi đội thuộc đúng một tập hợp. Anh ấy chọn một điểm tập trung cho mỗi tập hợp tại một tọa độ thực bất kỳ. Tất cả nhân viên trong cùng một đội phải đến cùng một điểm tập trung. Mỗi đội trong tập $A$ đi đến điểm tập trung của $A$, và mỗi đội trong tập $B$ đi đến điểm tập trung của $B$. Một trong hai tập hợp có thể rỗng.

Gọi $S_A$ là danh sách vị trí nhà của tất cả nhân viên thuộc các đội trong $A$, và định nghĩa $S_B$ tương tự cho $B$. Mỗi nhân viên được tính riêng biệt, ngay cả khi vị trí nhà trùng nhau.

Với một danh sách $S = (x_1, x_2, \ldots, x_m)$ gồm các vị trí nhà, tổng khoảng cách nhỏ nhất để các nhân viên này di chuyển đến một điểm tập trung là

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

Định nghĩa $M(S) = 0$ khi $S$ rỗng. Hãy giúp VegiCat cực tiểu hóa $M(S_A) + M(S_B)$ trên tất cả các cách chia các đội thành hai tập hợp.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 3 \cdot 10^5$), số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n$ và $k$ ($1 \le k \le n \le 3 \cdot 10^5$), lần lượt biểu thị số lượng nhân viên và số lượng đội.

Mỗi dòng trong $k$ dòng tiếp theo mô tả một đội. Dòng thứ $i$ chứa một số nguyên $m_i$ ($1 \le m_i \le n$), số lượng nhân viên trong đội $i$, theo sau là $m_i$ số nguyên $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), vị trí nhà của họ. Tổng của tất cả $m_i$ trong một bộ dữ liệu bằng $n$.

Vị trí nhà có thể lặp lại và có thể được cho theo bất kỳ thứ tự nào.

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $3 \cdot 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy in ra một số nguyên — tổng khoảng cách di chuyển nhỏ nhất có thể.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4
15

Ghi chú

Trong bộ dữ liệu đầu tiên, VegiCat cử đội $1$ đến điểm tập trung tại vị trí $1$ và đội $2$ đến điểm tập trung tại vị trí $8$. Các nhân viên trong mỗi đội di chuyển tổng khoảng cách là $2$, cho kết quả là $4$.

Trong bộ dữ liệu thứ hai, VegiCat chọn các điểm tập trung tại $3$ và $9$. Anh ấy cử đội $1$ và $2$ đến điểm tập trung đầu tiên, và đội $3$ đến điểm tập trung thứ hai. Các nhân viên trong các đội $1$, $2$ và $3$ di chuyển tổng khoảng cách lần lượt là $12$, $1$ và $2$, cho kết quả là $15$.