//Date 16/06/2021
//practice
#include <bits/stdc++.h>
using namespace std;

typedef  long long     ll;
typedef  vector<int>   vi;
typedef  pair<int,int> pii;

#define   all(x)        (x).begin(),(x).end()
#define   rep(i,a,b)    for(ll i = a; i<b ; i++)
#define   sz(x)         (int)((x).size())
#define   PI             3.141592653589
#define   mod            1000000007 
#define   MAX            1000005 //1e6+5
#define   ppc             __builtin_popcount
#define   ppcll           __builtin_popcountll
long long const INF = 1e13;

ll power(ll a, ll b) 
{   ll result =1;
    while(b)
    {   if(b%2) result=(result*a);    
        a=(a*a);
        b/=2;}
    return result;
}
void sol()
{
    int n; cin>>n;
    vector<int> arr(n);
    int sum = 0;
    rep(i,0,n) {cin>>arr[i];sum+=arr[i];}

    //SUBSET SUM PROBLEM
    bool dp[n+1][sum+1];
    for(int i=0;i<=n;i++)
    {
        dp[i][0] = true;
    }
    for(int i=1;i<=sum;i++)
    {
        dp[0][i] = false;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=sum;j++)
        {
            if(dp[i-1][j] == true) dp[i][j] = true; //1st condition
            else if(j-arr[i-1]>=0 && dp[i-1][j-arr[i-1]]) dp[i][j] = true; //2nd condition
            else dp[i][j] = false;
        }
    }
    int str = ceil(sum*1.0/2);
    for(int i = str;i<=sum;i++)
    {
        if(dp[n][i]) {cout<<i<<" "; return;}

    }

}
int main() 
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);cout.tie(NULL);
    int T=1; //cin>>T;
    while(T--) sol();
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(){
  bitset<100100> b;
  b.set(0);
  int n;
  cin >> n;
  int s = 0;
  for(int i = 0; i < n; i++){
    int x;
    cin >> x;
    b |= b<<x;
    s += x;
  }
  int ans = s;
  for(int i = 0; i <= s; i++)
    if(b[i])
      ans = min(ans, max(i, s - i));
  cout << ans << '\n';
  return 0;
}