D2. Черепаха и задача MEX (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Две версии — это разные задачи. В этой версии задачи нельзя выбирать одно и то же целое число дважды или более. Можно делать взломы только в том случае, если обе версии решены.

Однажды Черепаха играла с $$$n$$$ последовательностями. Пусть длина $$$i$$$-й последовательности равна $$$l_i$$$. Тогда $$$i$$$-я последовательность была $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$$$.

Свинка дала Черепахе задачу, когда Черепаха играла. Условие задачи было следующим:

  • Сначала было неотрицательное целое число $$$x$$$. Черепаха могла выполнять произвольное количество (возможно, ноль) операций с этим числом.
  • В каждой операции Черепаха могла выбрать целое число $$$i$$$, такое что $$$1 \le i \le n$$$ и $$$i$$$ не было выбрано ранее, и сделать $$$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)$$$). К сожалению, она не смогла решить эту задачу. Пожалуйста, помогите ей!

$$$^{\dagger}\text{mex}(c_1, c_2, \ldots, c_k)$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в последовательности $$$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)$$$.

Пример
Входные данные
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$$$ равным $$$\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$$$.