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