#include <bits/stdc++.h>
using namespace std;



#define ios			ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR(i,m)		for(int i = 0 ;i  < m ;i++)
#define mem(a ,b)		memset(a,  (b) , sizeof(a))
#define all(cont)		cont.begin(),cont.end()
#define mp			make_pair
#define pb			push_back
#define F			first
#define S			second
#define cn			cout<<'\n'
#define re			return 


typedef pair<int,int>		pi;
typedef	vector<int>		vi;
typedef long long 		ll;
typedef long double		ld;
typedef unsigned long long int  ull;

const int mod = 1e9 +7;
const int maxN = 1e5 + 1;

int n , m , w;


void solve(){
	cin >> n ;
	int a[n];
	ll sum = 0;
	for(int i= 0 ;i < n;i++){
		cin >> a[i];
		sum += a[i];
	}

	bool dp[n + 1][sum + 1];
	memset(dp , 0 , sizeof(dp));

	dp[0][0] = true;

	for(int i = 1 ;i <= n ;i++){
		for(int j = 0 ;j <= sum ;j++){
			dp[i][j] = dp[i-1][j];

			if(j - a[i-1] >= 0)dp[i][j] |= dp[i-1][j-a[i-1]];
		}
	}

	for(int j=  sum/2 ; j>= 0 ;j--){
		if(dp[n][j]){
			cout<<sum-j<<"\n";
			return;
		}
	}

}


int32_t main(){

	ios;



	int _t = 1;
//	cin >> _t;

	for(int i = 1 ; i  <= _t ;i++){
//		cout<< "Case #"<<i<<": ";
		solve();
	}


	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#ifndef aa
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
#define double long double
#define pii pair<int,int>
#define pdd pair<double,double>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define frev(a,b,c) for(int a=c; a>=b; a--)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
#define deb(x) cout << x << endl
#define done(x) {cout << x << endl;return;}
#define mini(x,y) x=min(x,y)
#define maxi(x,y) x=max(x,y)
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//const int mod = 998244353;
const int mod = 1e9 + 7;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
typedef vector<pair<int, int>> vpii;
typedef map<int, int> mii;
typedef set<int> si;
typedef set<pair<int,int>> spii;
typedef queue<int> qi;



const int N = 20;

int x[N], y[N], z[N], dp[1<<N];
vi g[1<<N];

int d(int i, int j){
   return abs(x[j]-x[i])+abs(y[j]-y[i])+max(0ll,z[j]-z[i]);
}

void solve() {

   int n;
   cin>>n;
   rep(i,0,n) cin>>x[i]>>y[i]>>z[i];
   dp[1] = 0;
   g[1] = {0,0};

   rep(msk, 3, 1<<n){
       if(msk%2==0)
          continue;
       vi v;
       int val = infl;
       rep(i,1,n){
          if(msk>>i&1 == 0) continue;
          int msk1 = msk ^ (1<<i);
          rep(j,0,sz(g[msk1])-1){
              int dis = dp[msk1] - d(g[msk1][j],g[msk1][j+1]) + d(g[msk1][j], i) + d(i, g[msk1][j+1]);
              //cout<<dis<<endl;
              if(dis>=val)continue;
              val = dis;
              v.clear();
              rep(k,0,j+1) v.pb(g[msk1][k]);
              v.pb(i);
              rep(k,j+1,sz(g[msk1])) v.pb(g[msk1][k]);
          }
       }
       dp[msk] = val;
       g[msk] = v;
       //cout<<dp[msk]<<endl;
   }

   
   cout<<dp[(1<<n)-1];     
  
   


}



signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    cout << fixed << setprecision(15);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
#ifdef aa
    cout << endl << endl << endl << endl << "Time elapsed: " << (double)(clock() - clk) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}



 
int powm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = (res*a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
 
 
int divide(int a, int b) {
    return (a % mod) * powm(b, mod - 2) % mod;
}



int norm(int a) {
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return a;
}


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