D2. 乌龟与 MEX 问题（困难版本）
单点时间限制：$2$ 秒
单点内存限制：$256$ 兆字节

两个版本是不同的题目。在这个版本的题目中，你不能两次或多次选择同一个整数 $i$。只有两个版本都通过时，你才能进行 Hack。

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

小猪在乌龟玩的时候给他出了一个题。题目描述如下：

一开始有一个非负整数 $x$。乌龟可以对 $x$ 进行任意多次（包括零次）操作。
每次操作中，乌龟可以选择一个整数 $i$（$1 \le i \le n$），且 这个 $i$ 之前没有被选过，并将 $x$ 设为

$$\operatorname{mex}(x, a_{i,1}, a_{i,2}, \dots, a_{i,l_i}) $$

其中 $\operatorname{mex}(c_1, c_2, \dots, c_k)$ 定义为最小的没有在序列 $c$ 中出现的非负整数。
例如，$\operatorname{mex}(2,2,0,3) = 1$，$\operatorname{mex}(1,2) = 0$。

乌龟被要求求出：在进行任意多次操作后，$x$ 可能达到的最大值。

乌龟不费力地解决了上述问题。他定义 $f(k)$ 为当 $x$ 的初始值为 $k$ 时上述问题的答案。

接着，小猪给乌龟一个非负整数 $m$，让他求出

的值。不幸的是，他没能解决这个问题。请你帮帮他！

输入
每个测试点包含多个测试用例。第一行包含测试用例的数量 $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}, \dots, a_{i,l_i}$（$0 \le a_{i,j} \le 10^9$）。

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

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

样例

输入

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

输出

16
18
1281
4
6556785365
1842836177961

注释

• 第一个测试用例：当 $x$ 初始为 $2$ 时，乌龟可以选择 $i=3$，将 $x$ 设为

  $$\operatorname{mex}(2, a_{3,1}, a_{3,2}, a_{3,3}, a_{3,4}) = \operatorname{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$ 设为

  $$\operatorname{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$，总和为 $3+1=4$。