Traveling Salesman with Alphabetical Order

In this problem, you are given an integer (N) representing the number of cities, a list of (N) city names, and an (N \times N) matrix of distances where the element (d_{ij}) represents the distance from city (i) to city (j). The cities are initially given in arbitrary order. Before finding the optimal route, sort the city names in alphabetical order and then consider all possible routes (i.e. all permutations of the sorted cities). Your task is to find the minimum total distance required to visit every city exactly once and return to the starting city.

The total distance for a route (r = (r_0, r_1, \dots, r_{N-1})) is given by: [ D(r) = d_{r_0, r_1} + d_{r_1, r_2} + \cdots + d_{r_{N-2}, r_{N-1}} + d_{r_{N-1}, r_0} ]

It is guaranteed that (1 \le N \le 10), so a brute force approach by trying all permutations is acceptable.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer (N), the number of cities.
• The second line contains (N) space-separated strings representing the names of the cities.
• The next (N) lines each contain (N) space-separated integers. The (j)-th integer in the (i)-th line represents the distance (d_{ij}) from the (i)-th city to the (j)-th city.

Note that the cities should first be sorted alphabetically before computing the route permutations.

outputFormat

Output a single integer representing the minimum total distance to travel through all cities exactly once and return to the starting city. The output should be printed to standard output.## sample

4
rome paris london berlin
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80