Hamiltonian cycle of minimal cost P42934

Given several directed graphs with $n$ vertices, each one described with a matrix $m$ of size $n \times n$ such that $m[i][j]$ is the cost of going from vertex $i$ to vertex $j$, calculate the minimum cost of the Hamiltonian cycles of every graph. A Hamiltonian cycle is a path that visits each vertex exactly once, and that ends at the starting vertex.

Input

Input consists of the description of several graphs. Each one begins with a natural number $n \ge 2$, followed by the matrix $n \times n$ of costs ($n$ lines, each with $n$ natural numbers, with zeroes at the diagonal).

Output

Print the minimum cost of the Hamiltonian cycles of every graph.