stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.0330810933010115x):
#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();



    vvl dp(n+1, vl(W+1, INF));  // i番目までで重さがjとなるときの価値の総和の最小値

    rep(i, n+1) {

        dp[i][0] = 0;

    }



    rep(i, n) {

        rep(j, W+1) {

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

            if(j >= weight[i]) {

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

            }

        }

    }



    out(dp[n][W]);

    re0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.9644037062658728x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.282657162101385x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.2533716301587143x):
#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;

}
// Slower C++ solution:
#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;



}

// Faster C++ solution for the same problem (measured speedup: 1.1116803770575505x):
#include <bits/stdc++.h>

using namespace std;





int main() {

	// your code goes here

	vector<int>v;

	int n;

	cin>>n;

	int dp[n+3];

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

	{

		dp[j]=INT_MAX;

	}

	int ans=0;

	v.push_back(1);

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

	{

		v.push_back(pow(9,j));

		v.push_back(pow(6,j));

	}

	dp[0]=0;

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

	{

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

		{

			if (v[j] <= i)

			 {

				    int sub_res = dp[i-v[j]];

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

            			 dp[i] = sub_res + 1;

			  }

		}

	}

	cout<<dp[n];

	return 0;

}
// Slower C++ solution:
#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;



}

// Faster C++ solution for the same problem (measured speedup: 1.2012500503972652x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.6080923498084703x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.7366134596100067x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.6861354368382564x):
#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);

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.6248191928150517x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.4974587929991725x):
//#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;

}