Лосеня
Лосеня
Нещодавно на краю Великого Флатландського Заповідника з'явився чарівний ліс, і одне дуже допитливе лосеня вирішило туди сходити. Після декількох годин блукання між зачарованими деревами лосеня вийшло з лісу і з тих пір стало набагато менш допитливим. Проте, повернувшись додому, лосеня виявило, що його роги значно збільшились у ширину. А так як відомо, що чим більші у лося роги, тим більший його вплив у лосиному товаристві, то інші лосі почали вимагати від лосенята детальну карту чарівного лісу.
По запевненням лосенятка, який напричуд добре запам'ятав усе, що з ним відбувалось, ліс поділено на N паралельних рядів, у i-му ряду знаходиться k_i дерев, причому лосеня точно вказало відстані між сусідніми деревами у кожному ряду. А так як ліс був чарівним, то коли лосеня проходило між деревами, відстань між якими була d, його роги збільшувались до d.
У силу прямолінійности свого характеру і вкрай бережливого відношення до своїх рогів усі лоси погодились, що по чарівному лісі можна рухатись лише вперед - від i ряду до i+1, причому ніякому лосю не можна проходити між деревами, якщо відстань між ними менша ширини його рогів. Тепер усім лосям (особливо лосям з маленькими рогами) цікаво, яка максимальна ширина рогів може бути у лося, який вишов з лісу, якщо вважати, що до входу у ліс ширина його рогів була рівна нулю.
Вхідні дані
У першому рядку знаходиться одне число N - кількість рядів дерев у лісі, 2 ≤ N ≤ 10^3. Наступні N рядків містять описи рядів. Перше число у i-му рядку k_i - кількість дерев у i-му ряду, 2 ≤ k_i ≤ 10^3. Далі записано k_i-1 цілих додатніх чисел, які не перевищують 10000 - відстані між сусідніми деревами у i-му ряду.
Вихідні дані
У вихідний файл виведіть одне число - максимальну довжину рогів лося, якщо з лісу можна вийти, або -1, якщо вийти з лісу неможливо.
Приклад
2 3 695 8210 2 1528
1528