J. Joint Relocation
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

VegiCat owns a company with $$$n$$$ employees in $$$k$$$ nonempty teams. The employees live along a straight road, represented by a number line. VegiCat wants to arrange two meeting points for them.

VegiCat divides the teams into two sets, $$$A$$$ and $$$B$$$, with each team in exactly one set. He chooses a meeting point for each set at any real coordinate. All employees on the same team must go to the same meeting point. Each team in set $$$A$$$ goes to the meeting point for $$$A$$$, and each team in set $$$B$$$ goes to the meeting point for $$$B$$$. Either set may be empty.

Let $$$S_A$$$ list the home positions of all employees on teams in $$$A$$$, and define $$$S_B$$$ similarly for $$$B$$$. Each employee is counted separately, even when home positions repeat.

For a list $$$S=(x_1,x_2,\ldots,x_m)$$$ of home positions, the minimum total distance for these employees to travel to one meeting point is $$$$$$ M(S)=\min_{p\in\mathbb{R}}\sum_{j=1}^{m}|x_j-p|. $$$$$$ Define $$$M(S)=0$$$ when $$$S$$$ is empty. Help VegiCat minimize $$$M(S_A)+M(S_B)$$$ over all ways to divide the teams into the two sets.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le 3\cdot10^5$$$), the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1\le k\le n\le 3\cdot10^5$$$), denoting the number of employees and the number of teams, respectively.

Each of the next $$$k$$$ lines describes one team. The $$$i$$$-th line contains an integer $$$m_i$$$ ($$$1\le m_i\le n$$$), the number of employees on team $$$i$$$, followed by $$$m_i$$$ integers $$$x_{i,1},\ldots,x_{i,m_i}$$$ ($$$1\le x_{i,j}\le10^7$$$), their home positions. The sum of all $$$m_i$$$ in a test case is $$$n$$$.

Home positions may repeat and may be given in any order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot10^5$$$.

Output

For each test case, output an integer — the minimum possible total travel distance.

Example
Input
2
4 2
2 1 3
2 8 10
8 3
3 4 12 1
2 3 2
3 9 8 10
Output
4
15
Note

In the first test case, VegiCat sends team $$$1$$$ to a meeting point at position $$$1$$$ and team $$$2$$$ to a meeting point at position $$$8$$$. The employees in each team travel a total distance of $$$2$$$, giving the answer $$$4$$$.

In the second test case, VegiCat chooses meeting points at $$$3$$$ and $$$9$$$. He sends teams $$$1$$$ and $$$2$$$ to the first meeting point, and team $$$3$$$ to the second. The employees in teams $$$1$$$, $$$2$$$, and $$$3$$$ travel total distances of $$$12$$$, $$$1$$$, and $$$2$$$, respectively, giving the answer $$$15$$$.