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.

Public test cases

**Input**

3 0 2 1 2 0 4 1 3 0 4 0 5 7 9 2 0 2 2 2 1 0 3 2 9 9 0

**Output**

6 12

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++