Пан Дивак якось зібрав певний капітал (вдало реалізувавши проект, за який не ризикував братися ніхто інший) і вирішив вкласти гроші у бізнес пасажирських перевезень. Він уже вибрав сукупність міст, між якими бажає організувати сполучення. Крім того, він твердо вирішив, що послідовності зупинок на його маршрутах завжди будуть впорядковані за словниковими правилами від найменшої назви до найбільшої («Словникові правила» означає, що при порівнянні слів порівнюються спочатку перші букви, якщо вони однакові,то другі, і т. д.) Знайомі переконали його, що це не завжди зручно (наприклад, Вінниця–Київ–Одеса– Полтава–Сімферополь–Ялта). Тому зараз пан Дивак розмірковує над компромісним варіантом: розробити два автобусні маршрути, так, щоб вони мали спільний початок (найменше за словниковим порядком місто) і кінець (найбільше за словниковим порядком місто), всередині кожного маршруту послідовності міст були впорядковані, і через кожне місто проходив хоча б один з двох маршрутів. Наприклад, для вищезгаданих міст це може бути пара маршрутів Вінниця–Київ–Полтава–Сімферополь–Ялта та Вінниця–Одеса–Сімферополь –Ялта.
Напишіть програму, яка допоможе пану Диваку прийняти рішення. Програма повинна, прочитавши таблицю відстаней між містами, знайти довжину маршруту, якщо просто відвідати усі міста по порядку, та мінімальну можливу сумарну довжину пари маршрутів, що задовольняє вимогам компромісного варіанту (обидва починаються в першому за словниковим порядком місті, закінчуються в останньому, всередині кожного маршруту всі міста відсортовані, через кожне місто проходить хоча б один з двох маршрутів).
Технічні умови. Програма 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