VegiCat は $k$ 個の空でないチームに分かれた $n$ 人の従業員がいる会社を経営しています。従業員たちは数直線として表されるまっすぐな道路沿いに住んでいます。VegiCat は彼らのために $2$ つの集合場所を手配したいと考えています。

VegiCat はチームを $2$ つの集合 $A$ と $B$ に分割し、各チームがちょうど一方の集合に属するようにします。彼は各集合に対して任意の実数座標に集合場所を $1$ つずつ選びます。同じチームのすべての従業員は同じ集合場所に行かなければなりません。 集合 $A$ に属する各チームは $A$ の集合場所へ行き、集合 $B$ に属する各チームは $B$ の集合場所へ行きます。どちらの集合も空であって構いません。

$A$ に属するチームの全従業員の自宅位置を並べたリストを $S_A$ とし、$B$ についても同様に $S_B$ を定義します。自宅位置が重複している場合でも、各従業員は別々に数えられます。

自宅位置のリスト $S = (x_1, x_2, \ldots, x_m)$ に対し、これらの従業員が $1$ つの集合場所へ移動するための最小の合計移動距離は

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

$S$ が空のときは $M(S) = 0$ と定義します。チームを $2$ つの集合に分割するすべての方法にわたって $M(S_A) + M(S_B)$ を最小化するよう VegiCat を助けてください。

入力

最初の行には、テストケースの個数を表す整数 $T$（$1 \le T \le 3 \cdot 10^5$）が与えられます。続いて各テストケースの説明が与えられます。

各テストケースの最初の行には、それぞれ従業員の数とチームの数を表す $2$ つの整数 $n$ と $k$（$1 \le k \le n \le 3 \cdot 10^5$）が与えられます。

続く $k$ 行はそれぞれ $1$ つのチームを説明します。$i$ 行目には、チーム $i$ の従業員数を表す整数 $m_i$（$1 \le m_i \le n$）と、それに続く彼らの自宅位置を表す $m_i$ 個の整数 $x_{i,1}, \ldots, x_{i,m_i}$（$1 \le x_{i,j} \le 10^7$）が与えられます。$1$ つのテストケースにおけるすべての $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$ となります。

$2$ 番目のテストケースでは、VegiCat は位置 $3$ と $9$ に集合場所を選びます。彼はチーム $1$ と $2$ を最初の集合場所へ、チーム $3$ を $2$ 番目の集合場所へ向かわせます。チーム $1$、$2$、$3$ の従業員の合計移動距離はそれぞれ $12$、$1$、$2$ となり、答えは $15$ となります。