Дерева у саду#4516
Центральний сад країни Олімпія настільки великий, що один садівник не в змозі його обслуговувати. Було прийнято рішення розділити сад на дві частини. Певні дерева будуть віднесені до першої частини, а ті, що залишаться, – до другої. Одна з частин саду може залишитись порожньою.
Між кожною парою дерев у саду протоптані стежки. Коли садівники йдуть від дерева до дерева, вони обов'язково йдуть по стежці, яка з'єднує безпосередньо ці два дерева. Довжина стежки однакова при переміщенні в обидві сторони.
Для спрощення роботи садівників, поділ вирішили проводити так, щоб довжина самої довгої стежки між парою дерев, які належать до однієї і тієї ж частини, була мінімальною.
Напишіть програму, яка за інформацією про довжини стежок між усіма парами дерев знаходить довжину самої довгої стежки між деревами з однієї частини саду, при оптимальному поділі саду на частини.
Перший рядок містить ціле число (2 \leq n \leq 1000) - кількість дерев у саду. Кожен -ий з наступних n - 1 рядків містить n - i чисел, які послідовно подають довжини стежок між -им деревом та деревами від i + 1-го до -го. Усі числа цілі, невід'ємні, і не перевищують 10^6.
Вивести одне ціле число - мінімальну для усіх можливих розбиттів саду довжину самої довгої стежки між деревами в одній з частин саду.
Приклад 1