Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

B. Оля и игра с массивами
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Артём предложил девочке Оле сыграть в следующую игру. Есть список из $$$n$$$ массивов, $$$i$$$-й массив содержит $$$m_i \ge 2$$$ целых положительных чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m_i}$$$.

Оля может переместить из каждого массива не более одного (возможно, $$$0$$$) числа в другой массив. Обратите внимание, перемещать числа из одного массива можно не более одного раза, однако добавлять числа в один массив можно несколько раз, а также, все перемещения выполняются одновременно.

Назовем красотой списка массивов величину $$$\sum_{i=1}^n \min_{j=1}^{m_i} a_{i,j}$$$. Иными словами, для каждого массива мы находим значение минимального элемента в нём, после чего суммируем получившиеся значения.

Суть игры — сделать красоту списка массивов максимально возможной. Помогите Оле победить в этой нелегкой игре!

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 25000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 25000$$$) — количество массивов в списке.

Далее следуют описания массивов. Каждое описание массива состоит из двух строк.

Первая строка содержит одно целое число $$$m_i$$$ ($$$2 \le m_i \le 50000$$$) — количество чисел в $$$i$$$-м массиве.

В следующей строке даны $$$m_i$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m_i}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — элементы $$$i$$$-го массива.

Гарантируется, что сумма $$$m_i$$$ по всем наборам входных данных не превосходит $$$50000$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальную красоту списка массивов, которую Оля может получить.

Пример
Входные данные
3
2
2
1 2
2
4 3
1
3
100 1 6
3
4
1001 7 1007 5
3
8 11 6
2
2 9
Выходные данные
5
1
19
Примечание

В первом наборе входных данных можно переместить число $$$3$$$ из второго массива в первый. Тогда красота равна $$$\min(1, 2, 3) + \min(4) = 5$$$. Можно показать, что это максимально возможная красота.

Во втором наборе входных данных есть всего один массив, поэтому независимо от перемещений красота равна $$$\min(100, 1, 6) = 1$$$.