#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
#define SZ(v) ((int)(v).size())
typedef pair<int,int> pii;
#define ll long long
int n;
const int Maxv=1e5+5;
bool dp[Maxv];
int main(){
	ios_base::sync_with_stdio(false);
  	cin.tie(NULL);
  	cin>>n;
  	dp[0]=1;
  	int tot=0;
  	for(int i=1;i<=n;i++){
  		int x;cin>>x;
  		tot+=x;
  		for(int j=Maxv-1;j>=0;j--){
  			if(dp[j]&&j+x<Maxv){
  				dp[j+x]=1;
			  }
		  }
	  }
	vector<int>v;
	for(int i=0;i<Maxv;i++){
		if(dp[i]){
			v.push_back(i);
		}
	}
	if(tot%2==1)tot++;
	auto it=lower_bound(v.begin(),v.end(),tot/2);
	cout<<*it<<endl;
	return 0;
}

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

int main() {
	int n;
	cin>>n;
	vector<int>set(n);
	int sum = 0;
	int x1= 0 ,x2 = 0;
	for(int i=0;i<n;i++){
		cin>>set[i];
		sum+=set[i];
	}
	bool subset[n + 1][sum + 1];
 
    // If sum is 0, then answer is true
    for (int i = 0; i <= n; i++)
        subset[i][0] = true;
 
    // If sum is not 0 and set is empty,
    // then answer is false
    for (int i = 1; i <= sum; i++)
        subset[0][i] = false;
 
    // Fill the subset table in botton up manner
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (j < set[i - 1])
                subset[i][j] = subset[i - 1][j];
            if (j >= set[i - 1])
                subset[i][j] = subset[i - 1][j]
                               || subset[i - 1][j - set[i - 1]];
        }
    }
    int mini = 1e8;
    int ans;
    for(int j=1;j<=sum;j++){
    	if(subset[n][j]){
    	//	cout<<j<<endl;
    		if(max(j,(sum-j))<mini){
    			mini = max(j,sum-j);
    			//mini = j-(sum-j);
    		}
    	}
    }
    cout<<mini<<endl;
    //cout<<max(ans,sum-ans)<<endl;
	
	
	
	
	return 0;
}