#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005

ll dp[105][maxn] , n, arr[105] , zog , vag;

ll solve(ll pos , ll sum)
{
    if(sum>vag)return 0LL;
    if(pos == n+1)
    {
        return sum;
    }
    if(dp[pos][sum]!=-1)return dp[pos][sum];

    ll ans1 = 0 , ans2 = 0;

    if(sum+arr[pos]<=vag)ans1 = solve(pos + 1 , sum + arr[pos]);
    ans2 = solve(pos + 1 , sum);



    return dp[pos][sum]=max(ans1 , ans2);
}

int main()
{
    scanf("%lld",&n);

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

    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&arr[i]);
        zog+=arr[i];
    }

    vag = zog/2;
    //cout << zog << endl;

    ll ans = solve(1 , 0);


    printf("%lld\n",zog-ans);
}

#include<bits/stdc++.h>
using namespace std;
#define I inline int
#define V inline void
#define ll long long int
#define isnum(ch) ('0'<=ch&&ch<='9')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define REP(u) for(int i=h[u],v;v=e[i].t,i;i=e[i].n)
#define gc (_op==_ed&&(_ed=(_op=_buf)+fread(_buf,1,100000,stdin),_op==_ed)?EOF:*_op++)
char _buf[100000],*_op(_buf),*_ed(_buf);
I getint(){
	int _s=0,_f=1;char _ch=gc;
	while(!isnum(_ch))(_ch=='-')&&(_f=-1),_ch=gc;
	while(isnum(_ch))_s=_s*10+_ch-48,_ch=gc;
	return _s*_f;
}
const int N=20,mod=998244353,INF=0x3f3f3f3f;
V check(int&x){x-=mod,x+=x>>31&mod;}
V cmax(int&x,int y){if(x-y>>31)x=y;}
V cmin(int&x,int y){if(y-x>>31)x=y;}
int n,now;
int X[N],Y[N],Z[N],dp[1<<N][N];
I dis(int x,int y){
	return abs(X[x]-X[y])+abs(Y[x]-Y[y])+max(0,Z[y]-Z[x]);
}
V input(){
	n=getint();
	FOR(i,0,n-1)X[i]=getint(),Y[i]=getint(),Z[i]=getint();
}
V init(){
	FOR(i,0,(1<<n)-1)FOR(j,0,n-1)dp[i][j]=INF;
	dp[1][0]=0;
}
V work(){
	int l=(1<<n)-1,u,v,t,flag;
	FOR(i,1,l){
		do{
			flag=0;
			FOR(u,0,n-1)FOR(v,0,n-1){
				t=1<<v|i;
				if(dp[i][u]+dis(u,v)<dp[t][v])
					dp[t][v]=dp[i][u]+dis(u,v),flag=1;
			}
		}while(flag);
	}
	cout<<dp[l][0];
}
int main(){
		input();
		init();
		work();
//	}
	return 0;
}