CF2003D2.Turtle and a MEX Problem (Hard Version)

两个版本的问题是不同的。在这个版本的问题中，你不能选择同一个整数两次或更多次。只有当两个版本都解决时，才能进行 hack。

有一天，乌龟正在玩 $n$ 个序列。设第 $i$ 个序列的长度为 $l_i$，则第 $i$ 个序列为 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$。

当乌龟在玩耍时，小猪给了他一个问题来解决。问题的陈述如下：

• 最初有一个非负整数 $x$。乌龟可以对这个整数执行任意次数（可能为零）的操作。
• 在每次操作中，乌龟可以选择一个之前未被选择过的整数 $i$（满足 $1 \le i \le n$），并将 $x$ 设为 $\text{mex}^{\dagger}(x, a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i})$。
• 乌龟被要求找到答案，即在执行任意次数操作后 $x$ 的最大值。

乌龟轻松解决了上述问题。他定义 $f(k)$ 为初始值 $x$ 为 $k$ 时上述问题的答案。

然后小猪给了乌龟一个非负整数 $m$，并要求乌龟找出 $\sum\limits_{i = 0}^m f(i)$ 的值（即 $f(0) + f(1) + \ldots + f(m)$ 的值）。不幸的是，他无法解决这个问题。请帮助他！

$\text{mex}(c_1, c_2, \ldots, c_k)$ 定义为不在序列 $c$ 中出现的最小非负整数 $x$。例如，$\text{mex}(2, 2, 0, 3)$ 是 $1$，$\text{mex}(1, 2)$ 是 $0$。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$（$1 \le n \le 2 \cdot 10^5, 0 \le m \le 10^9$）。

接下来的 $n$ 行每行包含若干个整数。第一个整数 $l_i$（$1 \le l_i \le 2 \cdot 10^5$）表示第 $i$ 个序列的长度，后面跟着 $l_i$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$（$0 \le a_{i, j} \le 10^9$）表示第 $i$ 个序列的元素。

保证所有测试用例中的 $n$ 之和不超过 $2 \cdot 10^5$，并且所有测试用例中的 $\sum l_i$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数 —— $\sum\limits_{i = 0}^m f(i)$ 的值。

在第一个测试用例中，当 $x$ 初始值为 $2$ 时，乌龟可以选择 $i = 3$ 并将 $x$ 设为 $\text{mex}(x, a_{3, 1}, a_{3, 2}, a_{3, 3}, a_{3, 4}) = \text{mex}(2, 7, 0, 1, 5) = 3$。可以证明乌龟无法使 $x$ 的值大于 $3$，因此 $f(2) = 3$。

可以看出 $f(0) = 3$，$f(1) = 3$，$f(2) = 3$，$f(3) = 3$，$f(4) = 4$。所以 $f(0) + f(1) + f(2) + f(3) + f(4) = 3 + 3 + 3 + 3 + 4 = 16$。

在第二个测试用例中，当 $x$ 初始值为 $1$ 时，乌龟可以选择 $i = 1$ 并将 $x$ 设为 $\text{mex}(x, a_{1, 1}, a_{1, 2}, a_{1, 3}, a_{1, 4}, a_{1, 5}) = \text{mex}(1, 0, 2, 0, 4, 11) = 3$。可以证明乌龟无法使 $x$ 的值大于 $3$，因此 $f(1) = 3$。

可以看出 $f(0) = 4$，$f(1) = 3$，$f(2) = 4$，$f(3) = 3$，$f(4) = 4$。所以 $f(0) + f(1) + f(2) + f(3) + f(4) = 4 + 3 + 4 + 3 + 4 = 18$。

在第四个测试用例中，可以看出 $f(0) = 3$ 和 $f(1) = 1$。所以 $f(0) + f(1) = 3 + 1 = 4$。