eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Лосеня

Лосеня

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Нещодавно на краю Великого Флатландського Заповідника з'явився чарівний ліс, і одне дуже допитливе лосеня вирішило туди сходити. Після декількох годин блукання між зачарованими деревами лосеня вийшло з лісу і з тих пір стало набагато менш допитливим. Проте, повернувшись додому, лосеня виявило, що його роги значно збільшились у ширину. А так як відомо, що чим більші у лося роги, тим більший його вплив у лосиному товаристві, то інші лосі почали вимагати від лосенята детальну карту чарівного лісу.

По запевненням лосенятка, який напричуд добре запам'ятав усе, що з ним відбувалось, ліс поділено на N паралельних рядів, у i-му ряду знаходиться k_i дерев, причому лосеня точно вказало відстані між сусідніми деревами у кожному ряду. А так як ліс був чарівним, то коли лосеня проходило між деревами, відстань між якими була d, його роги збільшувались до d.

У силу прямолінійности свого характеру і вкрай бережливого відношення до своїх рогів усі лоси погодились, що по чарівному лісі можна рухатись лише вперед - від i ряду до i+1, причому ніякому лосю не можна проходити між деревами, якщо відстань між ними менша ширини його рогів. Тепер усім лосям (особливо лосям з маленькими рогами) цікаво, яка максимальна ширина рогів може бути у лося, який вишов з лісу, якщо вважати, що до входу у ліс ширина його рогів була рівна нулю.

Вхідні дані

У першому рядку знаходиться одне число N - кількість рядів дерев у лісі, 2N10^3. Наступні N рядків містять описи рядів. Перше число у i-му рядку k_i - кількість дерев у i-му ряду, 2k_i10^3. Далі записано k_i-1 цілих додатніх чисел, які не перевищують 10000 - відстані між сусідніми деревами у i-му ряду.

Вихідні дані

У вихідний файл виведіть одне число - максимальну довжину рогів лося, якщо з лісу можна вийти, або -1, якщо вийти з лісу неможливо.

Приклад

Вхідні дані #1
2
3 695 8210
2 1528

Вихідні дані #1
1528
Автор Олексій Ципленков
Джерело NEERC-School 17.09.2011