English version is in beta. All contents of the site should be already translated (mostly using machine translation), and everything should work properly. However, if you find any problems, please contact me.
The problem statement has been automatically translated from Russian. If the statement is not clear, or you have any comments about it, please contact me. Anyway, I hope that someday I will fix the translation manually.

Royal Journey

His Majesty King Bubei II wished to go around his possessions. At the same time , there are the following wishes for the route:

1) the route should take the shortest possible time (royal time is a very valuable thing and it should be protected);

2) the route must include all localities exactly once (if the king misses a locality, then its inhabitants will be outraged by the royal inattention and will stop paying taxes; if the king visits a locality more than once, then the inhabitants of other localities will also be outraged)

3) the route should start and end in the capital of the state (after going around his possessions, the king should immediately get down to business). The capital is included in the route exactly 2 times: as a departure point and as a destination, it cannot be an intermediate settlement on the route.

Write a program that finds such a route according to the road scheme of the kingdom or determines that it is impossible to fulfill all the requirements.

Input data

first, enter the number $N$ (natural, does not exceed 10) – the number of settlements of the kingdom. Then follows $N$ rows of $N$ numbers in each – the travel time between settlements (time is a non–negative integer, does not exceed 500; if time = 0, it means that there is no path between some settlements). Locality No. 1 is the capital of the state.

Output data

print the smallest total time that His Majesty will spend on detouring his possessions, or the number -1 if it is impossible to build a route with the specified properties.

Examples
Input data
1
0
Output data
0
Input data
2
0 1
1 0
Output data
2
Input data
2
0 85 
85 0
Output data
170

This problem on informatics

algoprog.ru © Petr Kalinin, GNU AGPL, github.com/petr-kalinin/algoprog | About the license for the site materials | Blog (in Russian)