В некоторой компьютерной игре игрок управляет героем, который характеризуется одним целочисленным параметром — силой. Герою предстоит побеждать монстров, каждый из которых также характеризуется одним целочисленным параметром — бронёй.
На текущем уровне перед героем \(n\) пещер. Чтобы пройти уровень, герою нужно зайти во все пещеры в некотором порядке, в каждую ровно один раз, и выйти из каждой целым и невредимым. Когда герой зайдёт в пещеру \(i\), ему придётся подраться с \(k_i\) монстрами по очереди — сначала с монстром с бронёй \(a_{i, 1}\), потом с монстром с бронёй \(a_{i, 2}\) и так далее, в конце с монстром с бронёй \(a_{i, k_i}\).
Герой может победить монстра только в том случае, если сила героя строго больше брони монстра. Если герой не может победить монстра, с которым он дерётся, игра заканчивается и игрок проигрывает. Обратите внимание, что как только герой зашёл в пещеру, он не может из неё выйти, пока не подерётся со всеми монстрами в ней, причём именно в заданном порядке.
Каждый раз, когда герой побеждает монстра, сила героя увеличивается на \(1\).
Найдите минимальную необходимую силу, с которой герой должен начать уровень, чтобы иметь возможность зайти во все пещеры по одному разу в некотором порядке и победить всех монстров.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальный уровень силы героя, необходимый, чтобы иметь возможность зайти во все пещеры по одному разу в некотором порядке и победить всех монстров.
Примечание
В первом наборе входных данных нужно победить единственного монстра с бронёй \(42\), для этого достаточно иметь силу героя \(43\).
Во втором наборе входных данных герой с силой \(13\) может пройти уровень следующим образом:
- зайти в пещеру \(2\):
- победить монстра с бронёй \(12\), сила героя увеличится до \(14\);
- победить монстра с бронёй \(11\), сила героя увеличится до \(15\);
- зайти в пещеру \(1\):
- победить монстра с бронёй \(10\), сила героя увеличится до \(16\);
- победить монстра с бронёй \(15\), сила героя увеличится до \(17\);
- победить монстра с бронёй \(8\), сила героя увеличится до \(18\).