VegiCat 擁有一間公司，共有 $n$ 名員工，分為 $k$ 個非空團隊。員工們住在一條筆直的道路旁，這條道路可以用數線表示。VegiCat 想要為他們安排兩個集合點。

VegiCat 將這些團隊劃分為兩個集合 $A$ 與 $B$，每個團隊恰好屬於其中一個集合。他為每個集合在任意實數座標處選擇一個集合點。同一個團隊的所有員工必須前往同一個集合點。 集合 $A$ 中的每個團隊前往 $A$ 的集合點，集合 $B$ 中的每個團隊前往 $B$ 的集合點。任一集合都可以是空的。

令 $S_A$ 列出屬於 $A$ 中團隊的所有員工的住處位置，並類似地為 $B$ 定義 $S_B$。即使住處位置重複，每名員工仍會被分別計算。

對於一個住處位置列表 $S = (x_1, x_2, \ldots, x_m)$，這些員工前往同一個集合點的最小總移動距離為

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

當 $S$ 為空時，定義 $M(S) = 0$。請幫助 VegiCat 在將團隊劃分為兩個集合的所有方式中，最小化 $M(S_A) + M(S_B)$。

輸入格式

第一行包含一個整數 $T$（$1 \le T \le 3 \cdot 10^5$），代表測試資料的組數。接下來是各組測試資料的描述。

每組測試資料的第一行包含兩個整數 $n$ 與 $k$（$1 \le k \le n \le 3 \cdot 10^5$），分別代表員工的人數與團隊的數量。

接下來的 $k$ 行，每行描述一個團隊。第 $i$ 行包含一個整數 $m_i$（$1 \le m_i \le n$），代表團隊 $i$ 中的員工人數，接著是 $m_i$ 個整數 $x_{i,1}, \ldots, x_{i,m_i}$（$1 \le x_{i,j} \le 10^7$），代表他們的住處位置。每組測試資料中所有 $m_i$ 的總和為 $n$。

住處位置可能會重複，且可能以任意順序給定。

保證所有測試資料中 $n$ 的總和不會超過 $3 \cdot 10^5$。

輸出格式

對於每組測試資料，輸出一個整數——最小可能的總移動距離。

範例

輸入格式 1

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

輸出格式 1

4
15

說明

在第一組測試資料中，VegiCat 讓團隊 $1$ 前往位置 $1$ 的集合點，並讓團隊 $2$ 前往位置 $8$ 的集合點。每個團隊中的員工總移動距離皆為 $2$，因此答案為 $4$。

在第二組測試資料中，VegiCat 選擇在位置 $3$ 與 $9$ 設置集合點。他讓團隊 $1$ 與 $2$ 前往第一個集合點，讓團隊 $3$ 前往第二個集合點。團隊 $1$、$2$ 與 $3$ 中的員工總移動距離分別為 $12$、$1$ 與 $2$，因此答案為 $15$。