Его Величество Король Бубей Второй пожелал объехать свои владения. При этом к маршруту есть следующие пожелания:
1) маршрут должен занимать наименьшее возможное время (королевское время – вещь очень ценная и его надо беречь);
2) маршрут должен включать все населенные пункты ровно по одному разу (если король пропустит какой-то населенный пункт, то его жители будут возмущены королевским невниманием и перестанут платить налоги; если король посетит какой-то населенный пункт больше одного раза, то жители остальных населенных пунктов также возмутятся)
3) маршрут должен начинаться и заканчиваться в столице государства (объехав свои владения, король должен сразу приступить к делам). Столица входит в маршрут ровно 2 раза: как пункт отбытия и как пункт назначения, она не может являться промежуточным населенным пунктом маршрута.
Напишите программу, которая по схеме дорог королевства находит такой маршрут или определяет, что выполнить все требования невозможно.
Входные данные
Сначала вводится число
N (натуральное, не превышает 10) – количество населенных пунктов королевства. Затем следует
N строк по
N чисел в каждой – время пути между населенными пунктами (время – целое неотрицательное число, не превышает 500; если время = 0, то это означает, что пути между какими-то населенными пунктами нет). Населенный пункт №1 является столицей государства.
Выходные данные
Выведите наименьшее суммарное время, которое Его Величество потратит на объезд своих владений, или число -1, если построить маршрут с заданными свойствами невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
0
|
0
|
|
2
|
2
0 1
1 0
|
2
|
|
3
|
2
0 85
85 0
|
170
|