#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;


int main(){
  int n;
  cin >> n;
  vector<vector<int>> c(310,vector<int>(310));
  ll ans=0;
  rep(i,n)rep(j,n){ cin>>c[i][j]; ans+=c[i][j]; }

  rep(i,n)rep(j,n){ 
    bool flag=false;
    rep(k,n)if(i!=j && i!=k && j!=k){
      if(c[i][j]>c[i][k]+c[k][j]){ cout << -1 << endl; return 0; }
      if(c[i][j]==c[i][k]+c[k][j] && !flag){ ans-=c[i][j]; flag=true; continue; }
    }
  }
  cout << ans/2 << endl; 
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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 <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;


int main(){
  int n;
  cin >> n;
  vector<vector<int>> c(310,vector<int>(310));
  ll ans=0;
  rep(i,n)rep(j,n){ cin>>c[i][j]; ans+=c[i][j]; }

  rep(i,n)rep(j,n){ 
    bool flag=false;
    rep(k,n)if(i!=j && i!=k && j!=k){
      if(c[i][j]>c[i][k]+c[k][j]){ cout << -1 << endl; return 0; }
      if(c[i][j]==c[i][k]+c[k][j] && !flag){ ans-=c[i][j]; flag=true; continue; }
    }
  }
  cout << ans/2 << endl; 
  return 0;
}

```