Условие:
Робот-художник Піксель розробляє карти для настільної гри «Ticket to Ride». На карті є № міст, між кожною парою міст є залізничний маршрут. Для кожної пари міст (А, В) вартість проїзду від А до В така ж, як і вартість проїзду від В до А.
Деякі карти, створені Пікселем, вийшли занадто великими, тому він прийняв рішення розділити їх на дві непорожні частини. Певні міста будуть віднесені до першої частини, а решта до другої. Розділення треба провести так, щоб вартість найдорожчого маршруту між парою міст, що належать до однієї і тієї ж частини, була мінімальною.
Напишіть програму, яка за інформацією про вартості маршрутів між усіма парами міст, знайде вартість найдорожчого маршруту між містами з однієї частини, при оптимальному поділі карти на дві частини.
Формат вхідних даних
Перший рядок вхідних даних містить ціле число № (2 <= N <= 1000) кількість міст на карті. Кожен з наступних N - 1 рядків задає частину верхнього трикутника матриці вартостей: у і-му з них наведено рівно N - i цілих не від'ємних чисел вартості маршрутів між містом і та містами i + 1 i + 2 ,...,N. Усі вартості не перевищують 10 ^ 6
Формат вихідних даних
Виведіть одне число мінімальну для всіх можливих розбиттів карти вартість найдорожчого маршруту між містами в одній з частин карти.
