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

Деревья в саду

Деревья в саду

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

Для упрощения работы садовников, разделение решили проводить так, чтобы длина самой длинной тропинки между парой деревьев, принадлежащих одной и той же части, была минимальна.

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

Входные данные

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

Выходные данные

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

Пример

Входные данные #1
3
1 5
1
Выходные данные #1
1
Автор Владимир Ткачук
Источник 2007 XX Всеукраинская олимпиада по информатике, Кременчуг, Апрель 10 - 16, тур 1