#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio> 
#include<algorithm>
#define ll long long 
using namespace std;
const int maxn=510,inf=1e9;
ll n,m,x,y,z,tot,ans;
ll f[maxn][maxn],v[maxn][maxn];
void read(ll &k)
{
	int f=1;k=0;char c=getchar();
	while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
	k*=f;
}
int main()
{
	read(n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	read(f[i][j]),ans+=f[i][j];
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		if(i==j||i==k||j==k)continue;
		if(f[i][k]+f[k][j]<f[i][j])return puts("-1"),0;
		if(f[i][k]+f[k][j]==f[i][j])v[i][j]=v[j][i]=1;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(v[i][j])ans-=f[i][j];
	printf("%lld\n",ans>>1);
	return 0;
}
### Prompt

Your task is to create a cpp solution to the following problem:

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.

Examples

Input

3
0 1 3
1 0 2
3 2 0


Output

3


Input

3
0 1 3
1 0 1
3 1 0


Output

-1


Input

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


Output

82


Input

3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0


Output

3000000000

### Response

```cpp
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio> 
#include<algorithm>
#define ll long long 
using namespace std;
const int maxn=510,inf=1e9;
ll n,m,x,y,z,tot,ans;
ll f[maxn][maxn],v[maxn][maxn];
void read(ll &k)
{
	int f=1;k=0;char c=getchar();
	while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
	k*=f;
}
int main()
{
	read(n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	read(f[i][j]),ans+=f[i][j];
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		if(i==j||i==k||j==k)continue;
		if(f[i][k]+f[k][j]<f[i][j])return puts("-1"),0;
		if(f[i][k]+f[k][j]==f[i][j])v[i][j]=v[j][i]=1;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(v[i][j])ans-=f[i][j];
	printf("%lld\n",ans>>1);
	return 0;
}
```