Little D and Big D live on a simple undirected graph.

Unfortunately, this undirected graph is about to become a directed graph. Each of the two possible orientations for every edge has a specific cost. Little D and Big D decide to choose an orientation such that, regardless of which two vertices they are at, Little D can always reach Big D by traversing some directed edges. Based on this, they want to minimize the total cost.

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$ and $[a_{i,j}=-1]=[a_{j,i}=-1]$.

Output

A single integer representing the minimum cost. If no solution exists, 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

For $30\%$ of the data: $n \leq 7$.

For $60\%$ of the data: $n \leq 12$.

For $80\%$ of the data: $n \leq 16$.

For $100\%$ of the data: $1 \leq n \leq 18$, $-1 \leq a_{i,j} \leq 10^6$.