#include <bits/stdc++.h>
using namespace std;
#define ll long long
template <class T = ll> using V = vector<T>;
#define loop(n) while(n--)
#define rep(i,n) for(int i=0; i<(n);++i)
#define repp(i, l, r) for(int i = (l); i < (r); ++i)
#define all(v) (v).begin(), (v).end()
#define LL(n) int n;cin >> n

int main()
{
    LL(n);
    V<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));
    ll sum = accumulate(all(a), 0);
    sum = (sum+1)/2;

    bool dp[110][100010] = {};
    rep(i, 110) dp[i][0] = true;

    rep(i, n) rep(j, 100010){
        if(j - a[i] >= 0) dp[i+1][j] |= dp[i][j-a[i]];
        dp[i+1][j] |= dp[i][j];
    }

    rep(i, 100000){
        if(dp[n][i+sum]) {
            cout << i+sum << endl;
            break;
        }
    }

    return 0;
}

#include <chrono>
#include <thread>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define T top()
#define E end()
#define PS push
#define Q queue
#define PP pop()
#define L0 (LL)0
#define V vector
#define ST stack
#define FI first
#define MAX 4e18
#define MIN -MAX
#define DQ deque
#define SZ size()
#define C clear()
#define B begin()
#define F front()
#define SE second
#define DL double
#define G getline
#define IN insert
#define endl "\n"
#define EM empty()
#define cnn continue
#define MD 1000000007
#define PSB push_back
#define PI acos(-1.00)
#define PPB pop_back()
#define PSF push_front
#define ub upper_bound
#define lb lower_bound
#define PPF pop_front()
#define CF cout.flush()
#define line cout<<endl
#define LL long long int
#define one cout<<1<<endl
#define zer cout<<0<<endl
#define PQ priority_queue
#define kth find_by_order
#define nil cout<<-1<<endl
#define N cout<<"NO"<<endl
#define NN cout<<"No"<<endl
#define Y cout<<"YES"<<endl
#define fndidx order_of_key
#define YY cout<<"Yes"<<endl
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define MAU cout<<"Case "<<mau<<": "
#define SP(pre) fixed<<setprecision(pre)
#pragma GCC optimization ("unroll-loops")
#define MMAU cout<<"Case "<<mau<<":"<<endl
#define __lcm(A1,A2) (A1/(__gcd(A1,A2)))*A2
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
#define UOSMOY v.C;w.C;ww.C;uu.C;uo.C;vo.C;vu.C;ab.C;bc.C;cc.C;uuu.C;a.C;b.C;c.C;u.C
typedef tree<LL, null_type, less<LL>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define remembermeforcenturies using namespace std::chrono_literals;std::this_thread::sleep_for(-4611686018427387904ms);
V<LL>v,w,ab,bc;
set<LL>uo;
map<LL,LL>ww,cc,u;
V<pair<LL,LL> >uu,su;
map<LL,V<LL> >uuu;
map<pair<LL,LL>,LL> vo,vu;
map<LL,pair<LL,pair<LL,LL > > > vs;
priority_queue<LL,V<LL>,greater<LL> > moy;
LL dx[]= {-1,0,1,0,1,1,-1,-1};
LL dy[]= {0,1,0,-1,-1,1,1,-1};
LL dxx[]= {2,1,-1,-2,-2,-1,1,2};
LL dyy[]= {1,2,2,1,-1,-2,-2,-1};
LL dp[101][10001];
LL ar[10][10];
bool mat[110][100010];
void ans()
{

    LL sumOfArray = 0;
    for(LL i = 0; i < v.SZ; i++)
    {
        sumOfArray = sumOfArray + v[i];
    }
    LL sum = sumOfArray / 2;
    for(LL i = 0; i < v.SZ; i++)
    {
        mat[i][0] = true;
    }
    for(LL j = 0; j <= sum; j++)
    {
        if(j == v[0])
        {
            mat[0][j] = true;
        }
    }

    for(LL i = 1; i < v.SZ; i++)
    {
        for(LL j = 1; j <= sum; j++)
        {

            if(mat[i - 1][j])
            {
                mat[i][j] = true;
            }
            else
            {
                if(j >= v[i])
                {
                    mat[i][j] = mat[i - 1][j - v[i]];
                }
            }
        }
    }

    LL lastRow = v.SZ - 1;
    LL firstPartitionSum = -1;

    for(LL j = sum; j >= 0; j--)
    {
        if(mat[lastRow][j])
        {
            firstPartitionSum = j;
            break;
        }
    }

    LL secondPartitionSum = sumOfArray - firstPartitionSum;
    cout<<max(firstPartitionSum,secondPartitionSum)<<endl;
}

int main()
{
//  BRR;
//  file;
    FAST;
    char ch;
    string a,b,c;
    DL x,y,d,e,f,g,h;
    LL n,i,j,k,p,q,o,l,s,tt=1,m,t,z,aa,r=0;
//    cin>>tt;
    for(LL mau=1; mau<=tt; mau++)
    {
        UOSMOY;
        ordered_set os;
        remembermeforcenturies;
        cin>>n;
        for(i=0; i<n; i++)
        {
            cin>>o;
            v.PSB(o);
        }
        if(n==1)
        {
            cout<<v[0]<<endl;
            cnn;
        }
        sort(v.B,v.E);
        ans();


    }
    return 0;
    //IN
    //AL
}
