CF2003D1.Turtle and a MEX Problem (Easy Version)

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

一天，Turtle 正在玩 $n$ 个序列。第 $i$ 个序列的长度为 $l_i$，那么第 $i$ 个序列为 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$。

Piggy 在 Turtle 玩耍时给了他一个问题。问题的描述如下：

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

Turtle 很容易地解决了上述问题。他定义 $f(k)$ 为初始值为 $k$ 时上述问题的答案。

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

$^{\dagger}\text{mex}(c_1, c_2, \ldots, c_k)$ 定义为在序列 $c$ 中没有出现的最小非负整数。例如，$\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$ 时，Turtle 可以选择 $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$。可以证明 Turtle 无法使 $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$ 时，Turtle 可以选择 $i = 3$，将 $x$ 设为 $\text{mex}(x, a_{3, 1}, a_{3, 2}, a_{3, 3}, a_{3, 4}, a_{3, 5}) = \text{mex}(1, 1, 3, 0, 3, 3) = 2$，再选择 $i = 3$，将 $x$ 设为 $\text{mex}(2, 1, 3, 0, 3, 3) = 4$。可以证明 Turtle 无法使 $x$ 的值超过 $4$，因此 $f(1) = 4$。

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

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

由 ChatGPT 4.1 翻译