stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <algorithm>

#include <iostream>

using namespace std;



const int MAXN = 100001;

int dp[MAXN];



int rec_bank(int n) {

  int ret = n;

  if (n == 0)

    return 0;

  if (dp[n] != -1)

    return dp[n];



  for (int pow6 = 1; pow6 <= n; pow6 *= 6)

    ret = min(ret, rec_bank(n - pow6) + 1);

  for (int pow9 = 1; pow9 <= n; pow9 *= 9)

    ret = min(ret, rec_bank(n - pow9) + 1);

  return dp[n] = ret;

}



int main() {

  int N;

  cin >> N;

  for (int i = 0; i < MAXN; i++)

    dp[i] = -1;

  cout << rec_bank(N) << endl;

  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;



int f(int n, int base) {

  int ret = 0;

  while (n > 0) {

    int r = n % base;

    n /= base;

    ret += r;

  }

  return ret;

}



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int N;

  cin >> N;

  int minn = N;

  for (int i = 0; i < N + 1; i++)

    minn = min(f(N - i, 6) + f(i, 9), minn);

  cout << minn << '\n';

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



#define REP(i,a,b) for(int i=a;i<(int)b;i++)

#define rep(i,n) REP(i,0,n)

#define all(c) (c).begin(), (c).end()

#define zero(a) memset(a, 0, sizeof a)

#define minus(a) memset(a, -1, sizeof a)

#define watch(a) { cout << #a << " = " << a << endl; }

template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }

template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

template<class T> void operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) cin >> e; }



typedef long long ll;

int const inf = 1<<29;



constexpr int MaxK = 50;

int dp[100001];



int main() {



  rep(i, 100001) dp[i] = inf;

  dp[0] = 0;



  set<int> st;

  st.insert(1);

  rep(i, 8) st.insert(pow(6LL, i + 1));

  rep(i, 7) st.insert(pow(9LL, i + 1));



  int N; cin >> N;

  rep(i, N + 1) for (auto e: st) {

    if (i + e > N) continue;

    if (dp[i] == inf) continue;

    minimize(dp[i + e], dp[i] + 1);

  }

  cout << dp[N] << endl;

}


// Optimized solution to the same problem (faster):
# include <cstdio>

int N ;

int main ()

{

scanf ("%d" ,&N );

int res = N ;

for ( int i =0; i <= N ; i ++)

{

int cc =0;

int t = i ;

while (t >0) cc += t %6 , t /=6;

t=N - i ;

while (t >0) cc += t %9 , t /=9;

if ( res > cc ) res = cc ;

}

printf ("%d\n" , res );

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

using ll=long long;



const int MAX_N = 110000;



int memo[MAX_N]; 

int rec(int n) {

    if (n == 0) return 0; 

    if (memo[n] != -1) return memo[n];



    int res = n; 





    for (int pow6 = 1; pow6 <= n; pow6 *= 6) res = min(res, rec(n - pow6) + 1);



    

    for (int pow9 = 1; pow9 <= n; pow9 *= 9) res = min(res, rec(n - pow9) + 1);



    return memo[n] = res;

}



int main() {

    int N; cin >> N;



    for (int i = 0; i < MAX_N; ++i) memo[i] = -1;

    cout << rec(N) << endl;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h> 

using namespace std;

using ll=long long;

typedef pair<ll,ll> P;

#define fi first

#define se second

#define all(v) (v).begin(),v.end()

const ll mod=1000000007;

const ll mod2=998244353;

const ll inf=100000000000000000;

ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}

ll lcm(ll c,ll d){return c/gcd(c,d)*d;}

vector<int> dy={-1,0,1,0},dx={0,-1,0,1};

ll dp[1000010];

int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int n;

    cin>>n;

    fill(dp,dp+n,inf);

    dp[n]=0;

    vector<ll> tmp;

    tmp.push_back(1);

    ll six=6,nine=9;

    while(six<=n){

        tmp.push_back(six);

        six*=6;

    }

     while(nine<=n){

        tmp.push_back(nine);

        nine*=9;

    }

    sort(all(tmp));

    for(int i=n;i>=1;i--){

        for(int j=0;j<tmp.size();j++){

            if(i<tmp[j])break;

            dp[i-tmp[j]]=min(dp[i-tmp[j]],dp[i]+1);

        }

    }

    cout<<dp[0]<<endl;

}

   


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <string>

#include <algorithm>

#include <utility>

#include <cmath>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <functional>

using namespace std;

typedef long long ll;

typedef vector<ll> vl;

typedef vector<vector<ll>> vvl;

typedef pair<ll, ll> P;

typedef vector<vector<P>> vvP;

#define rep(i, n) for(ll i = 0; i < n; i++)

#define exrep(i, a, b) for(ll i = a; i <= b; i++)

#define out(x) cout << x << endl

#define exout(x) printf("%.10f\n", x)

#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)

#define all(a) a.begin(), a.end()

#define rall(a) a.rbegin(), a.rend()

#define pb push_back

#define re0 return 0

const ll mod = 1000000007;

const ll INF = 1e16;

const ll MAX_N = 100010;



ll dp[MAX_N];



ll f(ll i) {

    if(i == 0) {

        return 0;

    }

    if(dp[i] != -1) {

        return dp[i];

    }

    ll res = i;

    for(ll pow6 = 1; pow6 <= i; pow6 *= 6) {

        chmin(res, f(i - pow6) + 1);

    }

    for(ll pow9 = 1; pow9 <= i; pow9 *= 9) {

        chmin(res, f(i - pow9) + 1);

    }

    return dp[i] = res;

}



int main() {

    ll n;

    cin >> n;



    rep(i, MAX_N) {

        dp[i] = -1;

    }

    

    out(f(n));

    re0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <cstdio>

#include <string>

#include <algorithm>

#include <utility>

#include <cmath>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <functional>

using namespace std;

typedef long long ll;

typedef vector<ll> vl;

typedef vector<vector<ll>> vvl;

typedef pair<ll, ll> P;

typedef vector<vector<P>> vvP;

#define rep(i, n) for(ll i = 0; i < n; i++)

#define exrep(i, a, b) for(ll i = a; i <= b; i++)

#define out(x) cout << x << endl

#define exout(x) printf("%.10f\n", x)

#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)

#define all(a) a.begin(), a.end()

#define rall(a) a.rbegin(), a.rend()

#define pb push_back

#define re0 return 0

const ll mod = 1000000007;

const ll INF = 1e16;

const ll MAX_N = 100010;



int main() {

    ll W;

    cin >> W;



    vl weight;

    weight.pb(1);

    for(ll i = 6; i <= W; i *= 6) {

        weight.pb(i);

    }

    for(ll i = 9; i <= W; i *= 9) {

        weight.pb(i);

    }



    ll n = weight.size();



    vl dp(W+1, INF);  // 重さがjとなるときの価値の総和の最小値

    dp[0] = 0;

    rep(i, n) {

        for(ll j = weight[i]; j <= W; j++) {

            chmin(dp[j], dp[j - weight[i]] + 1);

        }

    }

    

    out(dp[W]);

    re0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;



const int INF = 1e9;



int main(){

    ll N; cin >> N;

    vector<int> memo;

    int dp[100001];

    for(int i = 0; i < 100001; i++) dp[i] = INF;

    int t1 = 6, t2 = 9;

    while(t1 < 100000){

        memo.push_back(t1);

        t1 *= 6;

    }

    while(t2 < 1e5){

        memo.push_back(t2);

        t2 *= 9;

    }

    memo.push_back(1);

    sort(memo.begin(), memo.end());

    for(auto itr: memo){

        dp[itr] = 1;

    }

    for(int i = 1; i <= N; i++){

        if(dp[i] == 1) continue;

        int j = 0;

        while(memo[j] < i){

            dp[i] = min(dp[i-memo[j]] + 1, dp[i]);

            j++;

        }

    }

    cout << dp[N] << endl;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



int main(){

    int N; cin >> N;

    int res = N;

    for(int i = 0; i <= N; i++){

        int cc = 0;

        int t = i;

        while(t > 0) cc += t % 6, t /= 6;

        t = N - i;

        while(t > 0) cc += t % 9, t /= 9;

        if(res > cc) res = cc;

    }

    cout << res << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

static const ll INF = 1ll<<60;



int main(){

    int N;

    cin>>N;

    vector<ll> dp(100000+10,INF);



    dp[0] = 0;



    for(int i=0; i<=N; i++){

        for(int six=1; six<=N; six *= 6){

            if(i-six < 0) continue;

            dp[i] = min(dp[i],dp[i-six]+1);

        }



        for(int nine=1; nine<=N; nine *= 9){

            if(i-nine < 0) continue;

            dp[i] = min(dp[i],dp[i-nine]+1);

        }

    }



    cout<<dp[N]<<endl;



    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

static const int INF = 1<<30;

static const int SIZE = 100000+10;



int main(){

    int n;

    cin>>n;

    vector<int> dp(SIZE,INF);

    dp[0] = 0;



    for(int i=1; i<=n; i++){

        

        for(int six=1; six<=i; six *= 6){

            if(i-six < 0) continue;

            dp[i] = min(dp[i],dp[i-six]+1);

        }



        for(int nine=1; nine<=i; nine *= 9){

            if(i-nine < 0) continue;

            dp[i] = min(dp[i],dp[i-nine]+1);

        }

    }



    cout<<dp[n]<<endl;



    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define mp              make_pair

#define pb              push_back

#define ff              first

#define ss              second

#define inc(A,B)        A=(A+(B))%MOD

#define mul(A,B)        (ll(A)*ll(B)%ll(MOD))

#define sub(a,b)        (((a)-(b)+MOD)%MOD)



typedef pair < int ,int > pii;

typedef long long ll;

typedef complex < ll > pt;



const int MAX_N = 100005;

const int MOD = 1e9 + 7;



int n, exponent;

int memo[MAX_N];



void update ( int &cant, int nextCant ) {

  if ( cant == -1 )

    cant = nextCant;

  else

    cant = min ( cant, nextCant );

}



void fillFor ( int num ) {

  for ( int i = 0; i <= n-num; ++i )

    if ( memo[i] != -1 )

      update ( memo[i+num], memo[i]+1 );

}



void doForExp ( int exponent, int bas ) {

  do {

    bas *= exponent;

    fillFor ( bas );

  } while ( bas <= n/exponent );

}



int main() {



//  freopen ( "in.txt" , "r" , stdin );

//  freopen ( "out.txt" , "w" , stdout );



  memset ( memo, -1, sizeof memo );

  scanf ( "%d", &n );



  memo[0] = 0;

  doForExp ( 6, 1 );

  doForExp ( 9, 1 );

  fillFor ( 1 );



  printf ( "%d\n", memo[n] );



  return 0;



}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define SC               scanf

#define PF               printf

#define ull              unsigned long long

#define ld               long double

#define D                double

#define F                first

#define S                second

#define pb               push_back

#define pf               push_front

#define MP               make_pair

#define sort_a(a)        sort(a.begin(),a.end());

#define sort_d(a)        sort(a.rbegin(),a.rend());

#define READ(f)          freopen(f, "r", stdin)

#define WRITE(f)         freopen(f, "w", stdout)

#define rev(s)           reverse(s.begin(),s.end())

#define it(it,mp)        for(auto it=mp.begin() ; it!=mp.end() ; it++)

#define IOS              ios_base :: sync_with_stdio(false); cin.tie(NULL);

const int N = 1e5 + 5;

const int inf = 1e9 + 1;

const double eps = 1e-15;

const double EPS = 1e-9;

const double PI = acos(-1.0);

typedef long long int                   ll;

typedef pair<int,int>                   PII;

int minCoins(int coins[], int m, int V)

{



    int table[V+1];



    table[0] = 0;

    for (int i=1; i<=V; i++)

        table[i] = INT_MAX;





    for (int i=1; i<=V; i++)

    {

        for (int j=0; j<m; j++)

          if (coins[j] <= i)

          {

              int sub_res = table[i-coins[j]];

              if (sub_res != INT_MAX && sub_res + 1 < table[i])

                  table[i] = sub_res + 1;

          }

    }

    return table[V];

}

int coins[]= {59049 , 46656,7776,6561,1296,729,216,81,36,9,6,1} ;

int main()

{

    IOS

    // READ("test.txt");

    //WRITE("");





    int sz = sizeof(coins)/sizeof(int) ;

    int need ;

    cin >> need;

    cout<< minCoins(coins,sz,need)<<endl;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



const int M = 1e5 + 1;



int memo[M];



int poww(int n, int p) {

    int ans = 1;

    while (p--)

        ans *= n;

    return ans;

}



int solve(int n) {

    if (!n)

        return 0;

    if (n < 0)

        return 1e9;



    int &r = memo[n];



    if (r == -1) {

        r = 1e9;



        for (int i = 1; i <= 5; i++)

            r = min(r, 1 + solve(n - poww(9, i)));



        for (int i = 1; i <= 6; i++)

            r = min(r, 1 + solve(n - poww(6, i)));



        r = min(r, 1 + solve(n - 1));

    }



    return r;

}



int main() {

    ios_base::sync_with_stdio(0);

    cin.tie(0);



    memset(memo, -1, sizeof memo);



    int n;

    cin >> n;

    cout << solve(n) << '\n';



    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define SC               scanf

#define PF               printf

#define ull              unsigned long long

#define ld               long double

#define D                double

#define F                first

#define S                second

#define pb               push_back

#define pf               push_front

#define MP               make_pair

#define sort_a(a)        sort(a.begin(),a.end());

#define sort_d(a)        sort(a.rbegin(),a.rend());

#define READ(f)          freopen(f, "r", stdin)

#define WRITE(f)         freopen(f, "w", stdout)

#define rev(s)           reverse(s.begin(),s.end())

#define it(it,mp)        for(auto it=mp.begin() ; it!=mp.end() ; it++)

#define IOS              ios_base :: sync_with_stdio(false); cin.tie(NULL);

const int N = 1e5 + 5;

const int inf = 1e9 + 1;

const double eps = 1e-15;

const double EPS = 1e-9;

const double PI = acos(-1.0);

typedef long long int                   ll;

typedef pair<int,int>                   PII;

int minCoins(int coins[], int m, int V)

{



    int table[V+1];



    table[0] = 0;

    for (int i=1; i<=V; i++)

        table[i] = INT_MAX;





    for (int i=1; i<=V; i++)

    {

        for (int j=0; j<m; j++)

          if (coins[j] <= i)

          {

              int sub_res = table[i-coins[j]];

              if (sub_res != INT_MAX && sub_res + 1 < table[i])

                  table[i] = sub_res + 1;

          }

    }

    return table[V];

}

int coins[]= {59049 , 46656,7776,6561,1296,729,216,81,36,9,6,1} ;

int main()

{

    IOS

    // READ("test.txt");

    //WRITE("");





    int sz = sizeof(coins)/sizeof(int) ;

    int need ;

    cin >> need;

    cout<< minCoins(coins,sz,need)<<endl;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;



int numTimes(int m, int d) {

    int n = m;

    int times = 0;

    for (int k = 6; k >= 0; k--) {

        int pow_d_k = (int)pow(d, k);

        if (pow_d_k <= n) {

            times += n / pow_d_k;

            n -= pow_d_k * (n / pow_d_k);

        }

    }

    return times;

}



int main() {

    int n;

    scanf("%d", &n);



    int ans = (1 << 21);



    int n_div_9 = n / 9;

    for (int ni = 0; ni <= n_div_9; ni++) {

        int si = (n - 9 * ni) / 6;

        int sum = 9 * ni + 6 * si;

        ans = min(ans, numTimes(ni, 9) + numTimes(si, 6) + (n - sum));

    }



    printf("%d\n", ans);

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;



int dp[100001] = {};



int main() {

    int n;

    scanf("%d", &n);

    

    dp[0] = 0;

    for (int p = 0; p <= n; p++) {

        for (int base = 9; base <= n; base *= 9) {

            if (p + base <= n) {

                dp[p+base] = dp[p+base] ? min(dp[p+base], dp[p] + 1) : dp[p] + 1;

            }

        }

        for (int base = 6; base <= n; base *= 6) {

            if (p + base <= n) {

                dp[p+base] = dp[p+base] ? min(dp[p+base], dp[p] + 1) : dp[p] + 1;

            }

        }

        dp[p+1] = dp[p+1] ? min(dp[p+1], dp[p] + 1) : dp[p] + 1;

    }



    printf("%d\n", dp[n]);



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int dp(int sum);

int n;

int memo[100009];



int main(){

  memset(memo,-1,sizeof(memo));

  cin>>n;

  cout<<dp(0)<<endl;

  return(0);

}



int dp(int sum){

  int t;

  if(memo[sum]!=-1)return memo[sum];

  if(sum==n)return 0;

  int rec=dp(sum+1)+1;

  t=6;

  while(sum+t<=n){

    rec=min(rec,dp(sum+t)+1);

    t*=6;

  }

  t=9;

  while(sum+t<=n){

    rec=min(rec,dp(sum+t)+1);

    t*=9;

  }

  return memo[sum]=rec;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

int dp[100009];



int main(){

  int n;

  cin>>n;

  for(int i=1;i<=n;i++){

    int s=6,t=9;

    dp[i]=dp[i-1]+1;

    

    while(i-s>=0){

      dp[i]=min(dp[i],dp[i-s]+1);

      s*=6;

    }

    while(i-t>=0){

      dp[i]=min(dp[i],dp[i-t]+1);

      t*=9;

    }

  }

  cout<<dp[n]<<endl;

  return(0);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

 

const int MAX_N = 110000;

 

int memo[MAX_N]; // memo[i] が i についての答え

 

int rec(int n){

  if(n == 0) return 0;

  if(memo[n] != -1) return memo[n];

  

  int res = n;

  

  for(int i=1; i<=n; i*=6) res = min(res, rec(n-i)+1);

  for(int j=1; j<=n; j*=9) res = min(res, rec(n-j)+1);

  

  return memo[n] = res;

}

 

int main(){

  int N; cin >> N;

  for(int i=0; i<MAX_N; i++) memo[i] = -1;

  cout << rec(N) << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <cstdlib>

using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



const long long INF = 1LL << 60;



int main(){

  int n; cin >> n;

  int dp[n];

  for(int i=0; i<=n; i++) dp[i] = n;

  dp[0] = 0;

  //cout << dp[3] << endl;

  

  for(int i=0; i<=n; i++){

    for(int pow6=1; pow6<=n; pow6*=6){

      if(i - pow6>=0) chmin(dp[i], dp[i - pow6] + 1);

    }

    for(int pow9=1; pow9<=n; pow9*=9){

      if(i - pow9>=0) chmin(dp[i], dp[i - pow9] + 1);

    }

    //chmin(dp[i+1], dp[i] + 1);

    //cout << dp[i] << endl;

  }

  

  cout << dp[n] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define Would

#define you

#define please







int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);



	

	int N;

	cin >> N;



	int A[301][301];

	rep1(i, N) {

		rep1(ii, N) {

			cin >> A[i][ii];

		}

	}



	int shouryaku[301][301] = {};

	rep1(k, N) {

		rep1(i, N) {

			rep1(j, N) {

				if (A[i][j] > A[i][k] + A[k][j]) {

					co(-1);

					Would you please return 0;

					//アホか！

				}

				else if (A[i][j] == A[i][k] + A[k][j] && i != k && j != k) {

					shouryaku[i][j] = 1;

				}

			}

		}

	}



	ll goukei = 0;

	rep1(i, N) {

		rep1(ii, N) {

			if(shouryaku[i][ii] == 0) goukei += A[i][ii];

		}

	}



	co(goukei / 2);



	Would you please return 0;

}

// Optimized solution to the same problem (faster):
//#include<bits/stdc++.h>

#include<cstdio>



using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}





int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint();



	int A[301][301];

	rep1(i, N) {

		rep1(ii, N) {

			A[i][ii] = getint();

		}

	}



	int shouryaku[301][301] = {};

	rep1(k, N) {

		rep1(i, N) {

			if (k == i) continue;

			rep1(j, N) {

				if (k == j) continue;

				if (A[i][j] > A[i][k] + A[k][j]) {

					printf("-1");

					return 0;

				}

				else if (A[i][j] == A[i][k] + A[k][j]) {

					shouryaku[i][j] = 1;

				}

			}

		}

	}



	ll goukei = 0;

	rep1(i, N) {

		rep1(ii, i - 1) {

			if (shouryaku[i][ii] == 0) goukei += A[i][ii];

		}

	}



	printf("%lld", goukei);



	Would you please return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define REP(i, n) for(int i = 0; i < n; i++)

#define REPR(i, n) for(int i = n; i >= 0; i--)

#define FOR(i, m, n) for(int i = m; i < n; i++)

#define ALL(obj) (obj).begin(), (obj).end()

#define INF 1e12

typedef long long ll;



int N;

vector<vector<bool>> A(300, vector<bool>(300,true));

vector<vector<ll>> dp(300, vector<ll>(300,INF));



int main() {

    cin >> N;



    REP(i,N){

        REP(j,N){

            cin >> dp[i][j];

        }

    }



    REP(i,N){

        REP(j,N){

            REP(k,N){

                if (j==k || k==i || i==j) continue;

                if (dp[j][k] > dp[j][i] + dp[i][k]){

                    cout << -1 << endl;

                    return 0;

                }else if (dp[j][k] == dp[j][i] + dp[i][k]){

                    A[j][k] = false;

                }

            }

        }

    }



    ll ans = 0;



     REP(i,N){

        REP(j,N){

            if (A[i][j]) ans += dp[i][j];

        }

    }



    cout << ans/2 << endl;



    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



#define REP(i, n) for(int i = 0; i < n; i++)

#define REPR(i, n) for(int i = n; i >= 0; i--)

#define FOR(i, m, n) for(int i = m; i < n; i++)

#define ALL(obj) (obj).begin(), (obj).end()

#define INF 1e9

typedef long long ll;





int main() {

    int N; cin >> N;

    vector<vector<pair<int,int>>> A(N, vector<pair<int,int>>(N));

    REP(i,N){

        REP(j,N){

            int a; cin >> a;

            A[i][j] = {a,0};

        }

    }



    REP(i,N-1){

        FOR(j,i+1,N){

            REP(k,N){

                if(i==k || j==k) continue;

                if(A[i][k].first+A[k][j].first < A[i][j].first){

                    cout << -1 << endl;

                    return 0;

                }else if(A[i][k].first+A[k][j].first == A[i][j].first){

                    A[i][j].second = 1;

                }

            }

        }

    }



    ll ans = 0;

    REP(i,N-1){

        FOR(j,i+1,N){

            if(A[i][j].second==0) ans += A[i][j].first;

        }

    }

    cout << ans << endl;

    return 0;

}

// Fastest known solution for this problem: