Господин Чудаков как-то собрал некий капитал (удачно реализовав проект, за который не рискнул взяться никто другой) и решил вложить деньги в бизнес пассажирских перевозок. Он уже выбрал совокупность городов, между которыми хочет организовать сообщение. Кроме того, он твёрдо решил, что последовательности остановок на его маршрутах всегда будут упорядочены лексикографически от наименьшего названия до наибольшего (<<лексикографически>> означает, что при сравнении слов сравниваются сначала первые буквы, если они одинаковы, то вторые, и т. д.). Знакомые убедили его, что это не всегда удобно (например, Винница--Киев--Одесса--Севастополь--Харьков--Ялта). Поэтому сейчас господин Чудаков размышляет над компромиссным вариантом: разработать два автобусных маршрута, так, чтобы они имели общее начало (лексикографически наименьший город) и конец (лексикографически наибольший город), внутри каждого маршрута последовательности городов были упорядочены, и через каждый город проходил хотя бы один из двух маршрутов. Например, для вышеуказанных городов это может быть пара маршрутов Винница--Киев--Харьков--Ялта и Винница--Одесса--Севастополь--Ялта. Напишите программу, которая поможет господину Чудакову принять решение. Программа должна, прочитав таблицу расстояний между городами, найти длину маршрута, если просто посетить все города по порядку, и минимально возможную суммарную длину пары маршрутов, удовлетворяющей требованиям компромиссного варианта (оба начинаются в лексикографически первом городе, заканчиваются в лексикографически последнем, внутри каждого маршрута все города отсортированы, через каждый город проходит хотя бы один из двух маршрутов). \InputFile Программа читает с клавиатуры сначала заданное число \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{2013}), затем \textbf{N--1} строк, \textbf{1}-ая из которых содержит \textbf{N--1} чисел, задающих расстояния от \textbf{1}-го города до \textbf{2}-го, \textbf{3}-го, ..., \textbf{N}-го, \textbf{2}-я --- \textbf{N--2} чисел (расстояния от \textbf{2}-го города до \textbf{3}-го, ..., \textbf{N}-го), и так до \textbf{(N--1)}-й строки, содержащей единственное число --- расстояние от \textbf{(N--1)}-го города до \textbf{N}-го. Все расстояния --- целые строго положительные числа, не превышающие \textbf{10^6}. Для расстояний гарантированно выполняется неравенство треугольника \textbf{d(i,j)+d(j,k)} ≥ \textbf{d(i,k)}. Названия городов во входном файле не упоминаются, но города уже упорядочены по возрастанию названий. \OutputFile Программа должна вывести на экран через пробел два числа --- длину маршрута, который проходит через все города в лексикографическом порядке, и минимально возможную суммарную длину компромиссной пары маршрутов.