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$。