两个版本是不同的问题。在此版本的问题中,您可以选择相同的整数两次或更多次。只有两个版本都解决了,你才能进行黑客攻击。
有一天,Turtle 正在玩 $$$n$$$ 序列。令第 $$$i$$$ 个序列的长度为 $$$l_i$$$。那么第 $$$i$$$ 个序列是 $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$$$。
当乌龟玩耍时,小猪给了乌龟一个需要解决的问题。问题的表述是:
- 首先有一个非负整数$$$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毫不费力地解决了上述问题。当$$$x$$$的初始值为$$$k$$$时,他将$$$f(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$$$ 中不出现的最小非负整数 $$$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)$$$ 的值。
示例
输入 #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
注意
在第一个测试用例中,当 $$$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}(x, a_{3, 1}, a_{3, 2}, a_{3, 3}, a_{3, 4}, a_{3, 5}) = \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$$$。