d__ and d__ want to t__ t__. There is an undirected graph with $n$ vertices and $m$ edges. Now, little q wants to orient each edge such that no matter which two vertices d__ and d__ are at, d__ can reach d__ by following these directed edges (i.e., the graph becomes strongly connected). Little q wants to know the minimum cost solution. Note that the two ways of orienting each undirected edge have different costs.

Input

The first line contains a positive integer $n$.

The next $n$ lines each contain $n$ integers, where the $j$-th number in the $i$-th line represents $a_{i,j}$, the cost of orienting the edge from $i$ to $j$. If there is no edge between $i$ and $j$, $a_{i,j}=-1$. It is guaranteed that $a_{i,i}=-1$.

Output

A single integer representing the minimum cost. If there is no solution, output $-1$.

Examples

Input 1

4
-1 3 2 -1
3 -1 7 7
5 9 -1 9
-1 6 7 -1

Output 1

27

Input 2

6
-1 1 2 -1 -1 -1
3 -1 4 -1 -1 -1
5 6 -1 0 -1 -1
-1 -1 0 -1 6 5
-1 -1 -1 4 -1 3
-1 -1 -1 2 1 -1

Output 2

-1

Constraints

It is guaranteed that $n\leq 18$.

• Subtask 1 (30 pts): $n\leq 7$.
• Subtask 2 (30 pts): $n\leq 12$.
• Subtask 3 (20 pts): $n\leq 16$.
• Subtask 4 (20 pts): No special restrictions.