PES16TSP - Solution for a Travelling Salesperson Problem

Find the shortest path from the first vertex traversing all other vertices in a complete graph and returning back to the first vertex.

Input

Input begins with n (1 ≤ n ≤ 11) of number of vertexes of a graph. The following n lines to have the cost matrix of the graph with n non-negative integers (0 ≤ cost ≤ 100) in each line separated by spaces.

Output

Print the cost of the shortest circuit starting at the first vertex and traversing through all other vertices of the complete graph.

Example

Input:
5
0 100 125 100 75
100 0 50 75 125
125 50 0 100 125
100 75 100 0 50
75 125 125 50 0

Output:
375

Added by:Prof. Channa Bankapur
Date:2016-01-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.