Экскурсионный тур
Город 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 всегда равно нулю.
Выходные данные
Выведите минимальную стоимость в строке.