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 $A_{u, 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 \leq N \leq 300$
• If $i ≠ j$, $1 \leq A_{i, j} = A_{j, i} \leq 10^9$.
• $A_{i, i} = 0$

Inputs

Input is given from Standard Input in the following format:

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}

Outputs

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