Hamiltonian cycle of minimal cost P42934

Given several directed graphs with n vertices, each one described with a matrix m of size n × 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 ≥ 2, followed by the matrix n × 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.