C. Самый нижний уровень
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

На текущем уровне перед героем $$$n$$$ пещер. Чтобы пройти уровень, герою нужно зайти во все пещеры в некотором порядке, в каждую ровно один раз, и выйти из каждой целым и невредимым. Когда герой зайдёт в пещеру $$$i$$$, ему придётся подраться с $$$k_i$$$ монстрами по очереди — сначала с монстром с бронёй $$$a_{i, 1}$$$, потом с монстром с бронёй $$$a_{i, 2}$$$ и так далее, в конце с монстром с бронёй $$$a_{i, k_i}$$$.

Герой может победить монстра только в том случае, если сила героя строго больше брони монстра. Если герой не может победить монстра, с которым он дерётся, игра заканчивается и игрок проигрывает. Обратите внимание, что как только герой зашёл в пещеру, он не может из неё выйти, пока не подерётся со всеми монстрами в ней, причём именно в заданном порядке.

Каждый раз, когда герой побеждает монстра, сила героя увеличивается на $$$1$$$.

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

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

Во входных данных находятся несколько наборов входных данных. В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных.

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

$$$i$$$-я из следующих $$$n$$$ строк содержит целое число $$$k_i$$$ ($$$1 \le k_i \le 10^5$$$) — число монстров в пещере $$$i$$$, за которым следуют $$$k_i$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, k_i}$$$ ($$$1 \le a_{i, j} \le 10^9$$$) — уровни брони монстров в том порядке, в котором герою предстоит с ними драться в пещере $$$i$$$.

Гарантируется, что сумма значений $$$k_i$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

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

Пример
Входные данные
2
1
1 42
2
3 10 15 8
2 12 11
Выходные данные
43
13
Примечание

В первом наборе входных данных нужно победить единственного монстра с бронёй $$$42$$$, для этого достаточно иметь силу героя $$$43$$$.

Во втором наборе входных данных герой с силой $$$13$$$ может пройти уровень следующим образом:

  • зайти в пещеру $$$2$$$:
    • победить монстра с бронёй $$$12$$$, сила героя увеличится до $$$14$$$;
    • победить монстра с бронёй $$$11$$$, сила героя увеличится до $$$15$$$;
  • зайти в пещеру $$$1$$$:
    • победить монстра с бронёй $$$10$$$, сила героя увеличится до $$$16$$$;
    • победить монстра с бронёй $$$15$$$, сила героя увеличится до $$$17$$$;
    • победить монстра с бронёй $$$8$$$, сила героя увеличится до $$$18$$$.