题目描述

有一张 $n$ 个点的无向图。现在要给每条无向边选择一个方向，使得定向后的有向图是强连通图，也就是说任意两个点 $u,v$ 之间，都能从 $u$ 沿有向边走到 $v$。

对于一条无向边 $(i,j)$，若把它定向为 $i\to j$，代价为 $a_{i,j}$；若定向为 $j\to i$，代价为 $a_{j,i}$。两种方向的代价可以不同。

请你求出使最终有向图强连通的最小总代价。如果不存在合法定向方案，输出 $-1$。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个数为 $a_{i,j}$：

• 若 $a_{i,j}\ne -1$，表示无向边 $\{i,j\}$ 存在，且将其定向为 $i\to j$ 的代价为 $a_{i,j}$；
• 若 $a_{i,j}=-1$，表示 $i,j$ 之间不存在边。

保证 $a_{i,i}=-1$。

输出格式

输出一行一个整数，表示最小总代价。若不存在使图强连通的定向方案，输出 $-1$。

样例 1

输入

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

输出

27

样例 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

输出

-1

数据范围与子任务

保证：