Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

## STSP - Small TSP

no tags

You're given a complete, directed, weighted graph with N vertices. Find the length of the shortest possible route visiting all the vertices exactly once, and returns to the original vertex.

### Input

The first line of input contains an integer N, the number of vertices. (N ≤ 18)

The rest of the input contains the (NxN) adjacency matrix of the graph.

The (i + 1)-th row, j-th column of the input contains the weight w(i, j) of the directed edge (i, j). (0 ≤ w(i, j) ≤ 1000000, w(i, i) = 0)

### Output

To the first and only line of output print the desired length.

### Example

```Input:
30 1 22 0 12 2 03
0 1 2
2 0 1
2 2 0

Output:
4```

 Added by: gustav Date: 2014-12-05 Time limit: 5s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: classical problem