#include <bits/stdc++.h>
#include <climits>
using namespace std;
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ps(x,y) fixed<<setprecision(y)<<x
#define int long long

int solve(int arr[],int n,int sum){
	bool dp[n+1][sum+1];
	memset(dp,false,sizeof(dp));
	for(int i=0;i<=n;i++){
		dp[i][0]=true;
	}
	for(int i=1;i<=n;i++){
		dp[0][i]=false;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=sum;j++){
			dp[i][j]=dp[i-1][j];
			if(arr[i-1]<=j){
				dp[i][j] |= dp[i-1][j-arr[i-1]];
			}
		}
	}
	for(int j=sum/2;j>=0;j--){
		if(dp[n][j]==true){
			return (sum-j);
		}
	}
	return -1;
}

int32_t main(){

	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	
	FIO;
	int n,sum=0;
	cin >> n;
	int arr[n];
	for(int i=0;i<n;i++) {
		cin >> arr[i];
		sum+=arr[i];
	}
	int ans = solve(arr,n,sum);
	cout << ans << "\n";
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b)  for(ll i=ll(a); i<=ll(b); i++)//  a<=i<=b i++ のforの開始
#define ALL(a) (a).begin(),(a).end()//全要素，min,max,findなどで使う
#define ITE(e,a,i) auto ite=find(ALL(a),e);\
 (i)=distance((a).begin(),ite);\
  if(ite==(a).end()) i=-1;
#define EACH(i,a) for(auto (i): (a))
#define ERASE(a,i) (a).erase((a).begin()+i);//iは0始まり
#define ERASES(a,i,j) (a).erase((a).begin()+i,(a).begin()+j);//i,jは0始まり i<= u <jの範囲を消す i!=j
#define SORT(a)  sort(begin(a),end(a))//小さい順にsort 1,2,3
#define SORT_(a) sort(begin(a),end(a),greater<ll>{})//大きい順にsort 5,4,3
#define OI(s) cout<<(s)<<endl
#define OII(s) printf("%8.7lf\n",(s));//double 小数点上8桁まで，下7桁まで出力
#define OI2(s0,s1) cout<<(s0)<<" "<<(s1)<<endl
#define OI3(s0,s1,s2) cout<<(s0)<<" "<<(s1)<<" "<<(s2)<<endl
#define OI4(s0,s1,s2,s3) cout<<(s0)<<" "<<(s1)<<" "<<(s2)<<" "<<(s3)<<endl
#define OIV(a) for(ll (iii)=0;(iii)<(a).size();(iii)++){cout<<(a)[(iii)]<<" ";} cout<<""<<endl
#define OIVV(a) for(ll (iii)=0;(iii)<(a).size();(iii)++){for(ll (jjj)=0;(jjj)<(a[(iii)]).size();(jjj)++){cout<<(a)[(iii)][(jjj)]<<" ";}cout<<" "<<endl;}
// vector<vector<ll>> a(5,vector<ll>(3,0));
//vector<vector<vector<double>>> abc(A, vector<vector<double>>(B, vector<double>(C,0)));
//vector<pair<ll,ll>> event;
// 20210606 Dまでいけなくてもいい，今週の成果をみせる





int main()
{
    ll N;
    cin >>N;
    vector<ll> T(N);
    ll sum=0;
    FOR(i,0,N-1) 
    {
        cin>>T[i]; 
        sum+=T[i];
    }
    if(N==1)
    {
        OI(T[0]);
        return 0;
    }

    vector<vector<bool>> dp(N,vector<bool>(sum+1,false));
    FOR(i,0,N-1) dp[i][0] = true;

    FOR(i,0,N-2)
    {
        FOR(j,0,sum)
        {  
            if(dp[i][j])
            {   // i番目を選ばない
                dp[i+1][j] = true;
                // i番目を選ぶ
                dp[i+1][j+T[i]] = true;

            }
        }
    }

    //OIVV(dp);

    ll S2;
    if(sum%2==0) S2=sum/2;
    else S2 = sum/2 +1;
    ll ans = 1000000000001;

    FOR(i,1,N-1)
    {
        FOR(j,S2,sum)
        {   
            //OI3(i,j,dp[i][j]);
            if(dp[i][j]) ans = min(j,ans);
        }
    }

    OI(ans);
    return 0;
}