#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MOD int(1e9+7)
#define INF int(1e9+7)
#define LINF ll(1e18+7)
#define PI acos(-1)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define P pair<ll,ll>
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

int n;
int x[20];
int y[20];
int z[20];
int dp[1<<20][20];
int c[20][20];

int main(){
  cin>>n;
  rep(i,n) cin>>x[i]>>y[i]>>z[i];
  rep(i,n)rep(j,n){
    c[i][j]=abs(x[j]-x[i])+abs(y[j]-y[i])+max(z[j]-z[i],0);
  }
  rep(i,1<<n)rep(j,n) dp[i][j]=INF;
  dp[1][0]=0;
  for(int S=2; S<(1<<n); S++){
    rep(i,n){
      if(S>>i&1){
        int T=S-(1<<i);
        rep(j,n){
          if(T>>j&1) chmin(dp[S][i],dp[T][j]+c[j][i]);
        }
      }
    }
  }
  int ans=INF;
  rep(i,n) chmin(ans,dp[(1<<n)-1][i]+c[i][0]);
  cout<<ans<<endl;
}
#include<bits/stdc++.h>
#define ll  long long int
#define db long double 
#define ull unsigned long long int
// #define mp make_pair
#define pii pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define all(a) a.begin(),a.end()
#define Nmax 1000005
#define INF 1000000000000000000
#define MOD 1000000007
#define MAXN 10000
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
 
using namespace std;

ll mod=1e7+7;
ll expo(ll base,ll exponent,ll mod){
    ll ans=1;
    while(exponent!=0){
        if(exponent&1) ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
        exponent>>=1;
    }
    return ans%mod;
}

ll seg[2000005];
ll lazy[2000005];
map<ll,ll>cod;

void push(ll v)
{
	if(lazy[v]==0) return;
	seg[2*v]+=lazy[v];
	lazy[2*v]+=lazy[v];
	seg[2*v+1]+=lazy[v];
	lazy[2*v+1]+=lazy[v];
	lazy[v]=0;
}

void update(ll v,ll tl,ll tr,ll l,ll r,ll val)
{
	if(l>tr || r<tl) return;
	if(l<=tl && tr<=r)
	{
		seg[v]+=val;
		lazy[v]+=val;
		return;
	}
	push(v);
	ll tm=(tl+tr)/2;
	update(2*v,tl,tm,l,r,val);
	update(2*v+1,tm+1,tr,l,r,val);
	seg[v]=min(seg[2*v],seg[2*v+1]);
}

ll query(ll v,ll tl,ll tr,ll l,ll r)
{
	if(tl>r || l>tr) return INF;
	// push(v);
	if(l<=tl && tr<=r)
	{
		return seg[v];
	}
	push(v);
	ll tm=(tl+tr)/2;
	return min(query(2*v,tl,tm,l,r),query(2*v+1,tm+1,tr,l,r));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tests=1;
    // cin>>tests;   
    while(tests--)
    {
    	ll i,j,n;
    	cin>>n;
    	vector<ll>a(n);
    	rep(i,0,n-1) cin>>a[i];
    	map<ll,ll>mpp;
    	rep(i,0,n-1) mpp[a[i]]++;
    	while(mpp.size()>1)
    	{
    		ll mn,mx;
    		ll secmx;
    		auto itr=mpp.begin();
    		mn=itr->first;
    		itr=mpp.end();
    		itr--;
    		mx=itr->first;
    		// mpp[mx]--;
    		// ll cnt=mpp[mx];
    		mpp.erase(mx);
    		// mpp[mx-mn]++;
    		itr--;
    		secmx=itr->first;
    		ll tmp=(mx-secmx+mn-1)/mn;
    		mx=mx-tmp*mn;
    		mpp[mx]++;
    	}
    	cout<<mpp.begin()->first;
    }
    time
    return 0;
}
    