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