Автобуси пана Чудакова
Господин Чудаков зібрав певний капітал, успішно реалізувавши проєкт, за який ніхто інший не наважився взятися, і вирішив інвестувати в бізнес пасажирських перевезень. Він вже обрав набір міст, між якими хоче організувати маршрути. Крім того, він вирішив, що послідовності зупинок на його маршрутах завжди будуть упорядковані лексикографічно від найменшої назви до найбільшої. Це означає, що при порівнянні слів спочатку порівнюються перші літери, якщо вони однакові, то другі, і так далі. Знайомі переконали його, що це не завжди зручно (наприклад, Вінниця–Київ–Одеса–Севастополь–Харків–Ялта). Тому зараз пан Чудаков розглядає компромісний варіант: розробити два автобусних маршрути, так, щоб вони мали спільний початок (лексикографічно найменше місто) і кінець (лексикографічно найбільше місто), всередині кожного маршруту послідовності міст були упорядковані, і через кожне місто проходив хоча б один з двох маршрутів. Наприклад, для вищезазначених міст це може бути пара маршрутів Вінниця–Київ–Харків–Ялта і Вінниця–Одеса–Севастополь–Ялта.
Напишіть програму, яка допоможе пану Чудакову прийняти рішення. Програма повинна, прочитавши таблицю відстаней між містами, знайти довжину маршруту, якщо просто відвідати всі міста по порядку, і мінімально можливу сумарну довжину пари маршрутів, що задовольняють вимогам компромісного варіанту (обидва починаються в лексикографічно першому місті, закінчуються в лексикографічно останньому, всередині кожного маршруту всі міста відсортовані, через кожне місто проходить хоча б один з двох маршрутів).
Вхідні дані
Програма читає з клавіатури спочатку задане число N (3 ≤ N ≤ 2013), далі N–1 рядків, 1-ий з яких містить N–1 чисел, що задають відстані від 1-го міста до 2-го, 3-го, ..., N-го, 2-ий — N–2 чисел (відстані від 2-го міста до 3-го, ..., N-го), і так до (N–1)-го рядка, що містить єдине число — відстань від (N–1)-го міста до N-го. Всі відстані — цілі строго додатні числа, що не перевищують 10^6. Для відстаней гарантовано виконується нерівність трикутника d(i,j)+d(j,k) ≥ d(i,k). Назви міст у вхідному файлі не згадуються, але міста вже упорядковані за зростанням назв.
Вихідні дані
Програма повинна вивести на екран через пробіл два числа — довжину маршруту, який проходить через всі міста в лексикографічному порядку, і мінімально можливу сумарну довжину компромісної пари маршрутів.