﻿

### Problem Statement

In Takahashi Kingdom, which once existed, there are N cities, and some pairs of cities are connected bidirectionally by roads. The following are known about the road network:

• People traveled between cities only through roads. It was possible to reach any city from any other city, via intermediate cities if necessary.
• Different roads may have had different lengths, but all the lengths were positive integers.

Snuke the archeologist found a table with N rows and N columns, A, in the ruin of Takahashi Kingdom. He thought that it represented the shortest distances between the cities along the roads in the kingdom.

Determine whether there exists a road network such that for each u and v, the integer Au, v at the u-th row and v-th column of A is equal to the length of the shortest path from City u to City v. If such a network exist, find the shortest possible total length of the roads.

### Constraints

• 1 ≤ N ≤ 300
• If i ≠ j, 1 ≤ Ai, j = Aj, i ≤ 109.
• Ai, i = 0

### Inputs

Input is given from Standard Input in the following format:

```N
A1, 1 A1, 2 ... A1, N
A2, 1 A2, 2 ... A2, N
...
AN, 1 AN, 2 ... AN, N
```

### Outputs

If there exists no network that satisfies the condition, print `-1`. If it exists, print the shortest possible total length of the roads.

```3
0 1 3
1 0 2
3 2 0
```

### Sample Output 1

```3
```

The network below satisfies the condition:

• City 1 and City 2 is connected by a road of length 1.
• City 2 and City 3 is connected by a road of length 2.
• City 3 and City 1 is not connected by a road.

```3
0 1 3
1 0 1
3 1 0
```

### Sample Output 2

```-1
```

As there is a path of length 1 from City 1 to City 2 and City 2 to City 3, there is a path of length 2 from City 1 to City 3. However, according to the table, the shortest distance between City 1 and City 3 must be 3.

Thus, we conclude that there exists no network that satisfies the condition.

```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
```

```82
```

### Sample Input 4

```3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0
```

### Sample Output 4

```3000000000
```

### Submitting .cpp to 'Restore Road'

Time Limit: 2 Seconds
Memory Limit: 1024MB