Две версии — это разные задачи. В этой версии задачи нельзя выбирать одно и то же целое число дважды или более. Можно делать взломы только в том случае, если обе версии решены.
Однажды Черепаха играла с \(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\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — значение \(\sum\limits_{i = 0}^m f(i)\).
Примечание
В первом наборе входных данных, когда \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
16
18
1281
4
6556785365
1842836177961
|