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

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

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

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

Вхідні дані

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

Вихідні дані

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