Две версии представляют собой разные задачи. В этой версии задачи вы можете выбрать одно и то же целое число дважды или более. Вы можете делать взломы только в том случае, если обе версии решены.
Однажды Черепаха играла с \(n\) последовательностями. Пусть длина \(i\)-й последовательности равна \(l_i\). Тогда \(i\)-я последовательность была \(a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}\).
Свинка дала Черепахе задачу, когда Черепаха играла. Условие задачи было следующим:
- Сначала было неотрицательное целое число \(x\). Черепаха могла выполнять произвольное количество (возможно, ноль) операций над этим числом.
- В каждой операции Черепаха могла выбрать целое число \(i\), такое что \(1 \le i \le n\), и сделать \(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\).
Примечание
В первом наборе входных данных, когда \(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 = 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\). Можно доказать, что Черепаха не может сделать значение \(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\).