题目描述

在曾经存在的高桥王国中，有 $N$ 个城市，一些城市之间通过双向道路相连。关于道路网络已知以下内容：

• 人们只能通过道路之间的道路在城市之间旅行。通过途中的城市，可以从任一城市到达任一其他城市。
• 不同的道路可能有不同的长度，但所有长度都是正整数。

考古学家Snuke在高桥王国的废墟中找到了一个 $N$ 行 $N$ 列的表 $A$。他认为，这代表了王国中的道路上城市之间的最短距离。

确定是否存在一个道路网络，使得对于每个 $u$ 和 $v$，$A$ 的第 $u$ 行 $v$ 列的整数 $A_{u, v}$ 等于从城市 $u$ 到城市 $v$ 的最短路径的长度。如果存在这样一个网络，找出道路的最短总长度。

约束条件

• $1 \leq N \leq 300$
• 如果 $i ≠ j$，则 $1 \leq A_{i, j} = A_{j, i} \leq 10^9$。
• $A_{i, i} = 0$

输入格式

输入通过标准输入给出，格式如下：

$N$
$A_{1, 1}$ $A_{1, 2}$ $...$ $A_{1, N}$
$A_{2, 1}$ $A_{2, 2}$ $...$ $A_{2, N}$
...
$A_{N, 1}$ $A_{N, 2}$ $...$ $A_{N, N}$

输出格式

如果不存在满足条件的网络，输出 -1。如果存在，输出道路的最短总长度。

示例输入1

3
0 1 3
1 0 2
3 2 0

示例输出1

3

以下网络满足条件：

• 城市 1 和城市 2 之间有一条长度为 1 的道路。
• 城市 2 和城市 3 之间有一条长度为 2 的道路。
• 城市 3 和城市 1 之间没有连接的道路。

示例输入2

3
0 1 3
1 0 1
3 1 0

示例输出2

-1

由于从城市 1 到城市 2 的路径长度为 1，并且从城市 2 到城市 3 的路径长度也为 1，因此从城市 1 到城市 3 的路径长度为 2。然而，根据表格，城市 1 和城市 3 之间的最短距离必须为 3。

因此，我们得出结论：不存在满足条件的网络。

示例输入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

示例输入4

3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

示例输出4

3000000000