You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

小明是一个顶级的特工，有一天他得到了一个情报图，记录着敌军的各阵地的最短路径长度信息，情报局有一个网格第 $i$ 行第 $j$ 列 $a_{i,j}$ 表示第 $i$ 个阵地到第 $j$ 个阵地的最短路径距离。特工想得到一个完整的地图 $b_{i,j}$ 表示第 $i$个阵地到第 $j$ 个阵地直接连接的双向路的长度（两个阵地之间可以没有路），可能有许多的地图可以满足 $a_{i,j}$ 的最短路径的信息，我们要求路的长度的总长度最短的那个地图。

当然从 $a_{i,j}$ 的最短路径的信息，不一定能合法的地图来对应，如果有合法的地图输出路可能的最短总长度，否则无解输出 $-1$ 。

【输入格式】

输入一行一个整数 $n$ 表示敌军的阵地数量。

接下来 $n$ 行，每行 $n$ 个数，代表 $a$ 数组，第 $i$ 行第 $j$ 列表示第 $i$ 个城市和第 $j$ 个城市间的最短路径。

【输出格式】

输出一行一个整数表示最短的路的总长度，没有合法方案输出 $-1$ 。

【样例输入1】

3
0 1 3
1 0 2
3 2 0

【样例输出1】

3

【样例输入2】

3
0 1 3
1 0 1
3 1 0

【样例输出2】

-1

【样例输入3】

5
0 21 18 11 28
21 0 13 10 26
18 13 0 23 13
11 10 23 0 17
28 26 13 17 0

【样例输出3】

82

【数据范围】

对于 $50\%$ 的数据， $n\le 5$

对于 $100\%$ 的数据， $n\le 300$

$i<或>j$ 时 $1\le a_{i,j}=a_{j,i}\le 10^9$

$i = j$ 时 $a_{i,j}=0$