Public Judge

pjudge

Time Limit: 5 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

小 D 和大 D 生活在一张简单无向图上。

很可惜,这张无向图马上就要变成有向图了。每条边的两种定向方式分别有一个代价,小 D 和大 D 决定找出一种定向方式,使得无论他们俩分别在哪两个点,小 D 都能走过一些有向边找到大 D,在这基础上,他们想要最小化代价总和。

输入格式

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

接下来 $n$ 行,每行 $n$ 个整数,其中第 $i$ 行第 $j$ 个数代表 $a_{i,j}$ ,表示定向为 $i$ 到 $j$ 的有向边的代价。如果不存在 $i,j$ 之间的边, $a_{i,j}=-1$ 。保证 $a_{i,i}=-1$ ,且 $[a_{i,j}=-1]=[a_{j,i}=-1]$。

输出格式

一行一个整数,表示最小代价。如果无解,输出 $-1$ 。

样例一

input

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

output

27

样例二

input

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

-1

数据范围与提示

对于 $30\%$ 的数据:保证 $n\leq 7$ 。

对于 $60\%$ 的数据:保证 $n\leq 12$ 。

对于 $80\%$ 的数据:保证 $n\leq 16$ 。

对于 $100\%$ 的数据:保证 $1\leq n\leq 18$,$-1\leq a_{i,j}\leq 10^6$。

时间限制:$\texttt{5s}$

空间限制:$\texttt{1GB}$