你决定搬家到一个新的地方，那里有一条笔直的道路。道路上有 $n$ 家商店，第 $i$ 家商店距离道路最左端的距离为 $x_i$。

你需要购买 $c$ 种杂货。对于每种杂货，购买它的成本是你家与出售该种杂货的最近商店之间的距离。你的总成本是每种杂货成本之和。

注意，即使你在同一家商店购买多种杂货，你仍然需要分别计算每种杂货的距离。

你需要选择一个位置来建造你的房子，以使总成本最小化。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, c$ ($1 \le n \le 10^5, 1 \le c \le 5 \cdot 10^5$)。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $t_i$ ($1 \le x_i \le 10^9, t_i \ge 1$)，分别表示第 $i$ 家商店的坐标以及该商店出售的杂货种类数量，随后是 $t_i$ 个不同的整数 $a_{i,1}, a_{i,2}, \dots, a_{i,t_i}$ ($1 \le a_{i,j} \le c$)，表示该商店出售的杂货种类。保证 $1, 2, \dots, c$ 在所有商店出售的杂货种类中至少出现一次。

对于每个测试用例，保证 $\sum t_i \le 5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示最小总成本。

样例

输入 1

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

输出 1

7