e-olymp
Змагання

DFS. Articulation points. Bridges

Дерева у саду

Центральний сад країни Олімпія настільки великий, що один садівник не в змозі його обслуговувати. Було прийнято рішення розділити сад на дві частини. Певні дерева будуть віднесені до першої частини, а ті, що залишаться, – до другої. Одна з частин саду може залишитись порожньою.

Між кожною парою дерев у саду протоптані стежки. Коли садівники йдуть від дерева до дерева, вони обов'язково йдуть по стежці, яка з'єднує безпосередньо ці два дерева. Довжина стежки однакова при переміщенні в обидві сторони.

Для спрощення роботи садівників, поділ вирішили проводити так, щоб довжина самої довгої стежки між парою дерев, які належать до однієї і тієї ж частини, була мінімальною.

Напишіть програму, яка за інформацією про довжини стежок між усіма парами дерев знаходить довжину самої довгої стежки між деревами з однієї частини саду, при оптимальному поділі саду на частини.

Вхідні дані

Перший рядок містить ціле число n (2n1000) - кількість дерев у саду. Кожен i-ий з наступних n - 1 -го рядків містить n - i чисел, які послідовно подають довжини стежок між i-им деревом та деревами від i + 1 -го до n-го. Усі числа цілі, невід'ємні, і не перевищують 106.

Вихідні дані

Вивести одне ціле число - мінімальну для усіх можливих розбиттів саду довжину самої довгої стежки між деревами в одній з частин саду.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані
3
1 5
1
Вихідні дані
1
Автор Володимир Ткачук
Джерело 2007 XX Всеукраїнська олімпіада з інформатики, Кременчук, Квітень 10 - 16, тур 1