VegiCat володіє компанією, у якій працюють $n$ співробітників, розподілених по $k$ непорожніх командах. Співробітники живуть уздовж прямої дороги, поданої числовою прямою. VegiCat хоче організувати для них дві точки збору.

VegiCat ділить команди на дві множини, $A$ і $B$, так, що кожна команда потрапляє рівно в одну множину. Для кожної множини він вибирає точку збору в довільній дійсній координаті. Усі співробітники однієї команди повинні прийти в ту саму точку збору. Кожна команда з множини $A$ прямує до точки збору для $A$, а кожна команда з множини $B$ прямує до точки збору для $B$. Будь-яка з множин може бути порожньою.

Нехай $S_A$ — список координат будинків усіх співробітників із команд множини $A$, а $S_B$ визначається аналогічно для $B$. Кожен співробітник враховується окремо, навіть якщо координати будинків повторюються.

Для списку $S = (x_1, x_2, \ldots, x_m)$ координат будинків мінімальна сумарна відстань, яку потрібно подолати цим співробітникам до однієї точки збору, становить

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

Визначимо $M(S) = 0$, коли список $S$ порожній. Допоможіть 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$.