Екскурсійний тур
Місто KM має N туристичних зон. Наразі кожна пара зон з'єднана двосторонньою дорогою.
Однак з певних причин пан KM, мер цього міста, вирішив зробити всі ці дороги односторонніми. Перебудова дороги між зоною i та зоною j в односторонню дорогу від зони i до зони j коштує C_ij доларів. Звісно, пан KM є економним і хоче мінімізувати загальну вартість перебудови.
З іншого боку, оскільки туризм є найважливішою галуззю для міста KM, має існувати тур, що проходить через усі туристичні зони, відвідуючи кожну зону рівно один раз. Перша та остання зона маршруту не обов'язково повинні бути однаковими. Чи можете ви розрахувати мінімальну загальну вартість, необхідну для перебудови, враховуючи цю ситуацію?
Вхідні дані
У першому рядку міститься кількість туристичних зон N (1 ≤ N ≤ 100). Наступні N рядків описують цілочислову матрицю C, де j-й елемент i-го рядка вхідних даних описує C_ij (0 ≤ Cij ≤ 1000000). Для кожного i можна припустити, що C_ii завжди дорівнює нулю.
Вихідні дані
Виведіть мінімальну вартість в одному рядку.