Far Away from Home

You have decided to move your house to a new place, by a straight road. There are $n$ stores lying on the road. The $i$-th store has a distance $x_i$ to the leftmost of the road.

There are $c$ types of groceries you need to buy. For each type, your cost to buy it is the distance between your house and the nearest store which sells this. Your total cost is the sum of costs of each type.

Note that even you may buy some types of groceries in the same store, you still need to calculate the distance multiple times.

You need to choose a place for your house to minimize the total cost.

Each test contains multiple test cases. The first line contains an integer $T$ ($1\le T\le 5$) denoting the number of test cases.

For each test case, the first line contains two integers $n, c$ ($1\le n\le 10^5$, $1\le c\le 5\cdot 10^5$).

The next $n$ lines each, contains two integers $x_i$ and $t_i$ first ($1\le x_i\le 10^9$, $t_i\ge 1$), denoting the coordinate of store $i$ and the number of types of groceries store $i$ sells, and following $t_i$ distinct integers $a_{i,1},a_{i,2},\cdots,a_{i,t_i}$ ($1\le a_{i,j}\le c$), denoting the types of groceries store $i$ sells. It is guaranteed that $1,2,\cdots ,c$ each appears at least once in all the types the stores sell.

**For each test case**, it is guaranteed that $\sum t_i\le 5\cdot 10^5$.

For each test case, output one line with an integer, denoting the minimum total cost.

1
4 4
1 1 4
5 1 4
9 3 1 3 4
2 2 2 3

7

2023“钉耙编程”中国大学生算法设计超级联赛（10）