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