E. Gluing Pluto Back Together
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Luna is a space explorer who has spent the last few years traveling through the vast expanse of the universe in search of new and exciting discoveries. She has visited countless planets, but her most recent find is one that has truly captivated her.

Luna has just discovered a number of space rocks and would like to form a new planet by gluing them in a ring. Specifically, she has found $$$N$$$ pieces of rock numbered from $$$1$$$ to $$$N$$$. Luna's mission is to glue the rocks together to form the planet. However, the cost of gluing each pair of adjacent rocks varies.

Luna has gathered data on the costs for each pair of rocks and is now faced with the challenge of building the planet while minimizing the overall cost. Gluing rocks $$$i$$$ and $$$j$$$ together costs $$$C_{i,j} = C_{j,i}$$$.

In order to minimize the cost of building the planet, Luna needs to find the optimal order in which to glue the rocks. She must ensure that the sequence of rocks forms a connected cycle. Your task is to help Luna determine the minimum cost to build this new ring planet.

Input

The first line of input contains an integer $$$N$$$ $$$(2 \leq N \leq 12)$$$ - the number of rocks on the planet.

Each of the next $$$N$$$ lines contains $$$N$$$ integers representing the cost to glue each rock to the other rocks. Each cost is a non-negative integer not exceeding $$$10^5$$$.

Output

Output a single integer - the minimum cost to build the planet.

Example
Input
4
0 1 2 3
1 0 4 5
2 4 0 6
3 5 6 0
Output
14