MEX 变换

题目描述

Y 同学最近迷上了一个关于序列和 MEX（最小排斥数）的数学游戏。

此时，桌面上摆放着 $N$ 个整数序列。第 $i$ 个序列的长度为 $l_i$，其元素记为 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$。

游戏规则如下：

1. 初始时，给定一个非负整数 $x$。
2. Y 同学可以对 $x$ 进行任意次数（包括 $0$ 次）的操作。
3. 在每一次操作中，Y 同学可以自由选择 $N$ 个序列中的任意一个（设为第 $i$ 个序列），然后将 $x$ 更新为 $x$ 与该序列所有元素的 MEX 值。 即：$x \leftarrow \text{mex}(x, a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i})$。 注意：同一个序列可以在不同的操作中被多次选择。

Y 同学定义 $f(k)$ 为：当初始整数为 $k$ 时，经过若干次操作后，能够得到的 $x$ 的最大值。

现在，Y 同学得到了一个非负整数 $M$。他的任务是计算 $0$ 到 $M$ 之间所有整数作为初始值时的答案之和，即求：

请你帮助 Y 同学完成这个计算。

关于 MEX 的定义： 对于一个整数集合（或序列），$\text{mex}$ 定义为该集合中没有出现过的最小非负整数。 例如：$\text{mex}(2, 2, 0, 3) = 1$，$\text{mex}(1, 2) = 0$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含两个整数 $N$ 和 $M$，分别表示序列的个数和求和的上限。 接下来 $N$ 行，每行描述一个序列。 每行的第一个整数 $l_i$ 表示第 $i$ 个序列的长度。 紧接着是 $l_i$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$，表示序列中的元素。

输出格式

对于每组测试数据，输出一行一个整数，表示 $\sum_{k=0}^{M} f(k)$ 的值。

样例

样例输入 #1

6
3 4
2 0 2
3 2 3 3
4 7 0 1 5
3 4
5 0 2 0 4 11
1 1
5 1 3 0 3 3
2 50
2 1 2
2 1 2
1 1
7 1 2 4 1 4 9 5
4 114514
2 2 2
5 7 3 6 0 3
3 0 1 1
5 0 9 2 1 5
5 1919810
1 2
2 324003 0
3 1416324 2 1460728
4 1312631 2 0 1415195
5 1223554 192248 2 1492515 725556

样例输出 #1

16
20
1281
6
6556785365
1842836177961

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 10^4$
• $1 \le N \le 2 \times 10^5$
• $0 \le M \le 10^9$
• $1 \le l_i \le 2 \times 10^5$
• $0 \le a_{i, j} \le 10^9$
• 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$。
• 所有测试用例中 $\sum l_i$ 的总和不超过 $2 \times 10^5$。