Пан Чудак как-то собрал некий капитал (удачно реализовав проект, за который не рискнул взяться никто другой) и решил вложить деньги в бизнес пассажирских перевозок. Он уже выбрал совокупность городов, между которыми хочет организовать сообщение. Крому того, он твердо решил, что последовательности остановок на его маршрутах всегда будут упорядочены по словарным правилам от наименьшего названия до наибольшего («Словарные правила» означает, что при сравнении слов сравниваются сначала первые буквы, если они одинаковы, то вторые, и т. д.). Знакомые убедили его, что это не всегда удобно (например, Винница–Киев–Одесса– Полтава–Симферополь–Ялта). Поэтому сейчас пан Чудак размышляет над компромиссным вариантом: разработать два автобусных маршрута, так, чтобы они имели общее начало (наименьший по словарному порядку город) и конец (наибольший по словарному порядку город), внутри каждого маршрута последовательности городов были упорядочены, и через каждый город проходил хотя бы один из двух маршрутов. Например, для вышеуказанных городов это может быть пара маршрутов Винница–Киев–Полтава–Симферополь–Ялта и Винница–Одесса–Симферополь –Ялта.
Напишите программу, которая поможет пану Чудаку принять решение. Программа должна, прочитав таблицу расстояний между городами, найти длину маршрута, если просто посетить все города по порядку, и минимально возможную суммарную длину пары маршрутов, удовлетворяющей требованиям компромиссного варианта (оба начинаются в первом по словарному порядку городе, заканчиваются в последнем, внутри каждого маршрута все города отсортированы, через каждый город проходит хотя бы один из двух маршрутов).
Технические условия. Программа Towns читает с клавиатуры сначала заданное число N (3 ≤ N ≤ 555), затем N∙(N–1) / 2 чисел, задающих расстояния (от 1‑го города до 2‑го, 3‑го, …, N‑го, затем от 2‑го до 3‑го, …, N‑го, и т. д.). Расстояния натуральны (целые строго положительные) числами, не большими 106. Все числа записаны в одной строке, разделены пробелами. Для расстояний гарантированно выполняется неравенство d(i,j)+d(j,k) ≥d(i,k).
Программа должна вывести на экран через пробел два числа — длину маршрута, который проходит через все города в словарном порядке и минимально возможную суммарную длину компромиссной пары маршрутов.
Пример
Ввод:
5 1 8 6 3 7 5 2 11 7 5
Вывод
24 26