// Disclaimer: Don't copy my template, it may lead to plagiarism.
/* Author: Soumy Jain
   Handle: soumy_jain || soumyjain
   "Beautiful flowers too, eventually wither and fall. That's the fate of all living beings."
   "I hate perfection. To be perfect is to be unable to improve any furthur." - Mayuri Kurotsuchi | Bleach
   "I smile to show the pressure of heroes and to trick the fear inside of me."
   "Gravel may be gravel, but me? I'm the gravel that shatters diamonds."
   "If you were to write a story with me in the lead role, it would certainly be...a TRAGEDY." - Kaneki Ken | Tokyo
   Ghoul
*/
/******************************************************************************/
// clang-format off
#include <bits/stdc++.h>
#define ll        long long
#define ull       unsigned long long
#define SPEEDHACK ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff        first
#define ss        second
#define sz(v)     (ll)(v).size()
#define file      freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define MOD       1000000007      // 998244353
using namespace std;
/******************************************************************************/
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(ll x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(ull x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename T, typename V>
void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'; }
template<typename T>
void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}"; }
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
// clang-format on

/***********************************MAIN***************************************/
// Are you ready to face the wrath of test cases? Good luck noob Soumy!

int minDifference(vector<ll> &arr, int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    bool dp[n + 1][sum / 2 + 1];
    for (int i = 0; i <= n; i++)
    {
        dp[i][0] = true;
    }
    for (int i = 1; i <= sum / 2; i++)
    {
        dp[0][i] = false;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= sum / 2; j++)
        {
            if (arr[i - 1] <= j)
                dp[i][j] = dp[i - 1][j - arr[i - 1]] || dp[i - 1][j];
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    int mn = INT_MAX;
    for (int i = 1; i <= sum / 2; i++)
    {
        if (dp[n][i])
            mn = min(mn, sum - 2 * i);
    }
    return mn == INT_MAX ? arr[0] : mn;
}

void work()
{
    ll n, sum = 0;
    cin >> n;
    vector<ll> v(n);
    for (auto &i : v)
        cin >> i, sum += i;
    ll x = minDifference(v, n);
    cout << (minDifference(v, n) + sum) / 2;
}

int main()
{
    SPEEDHACK
    // file
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        work();
    }
    return 0;
}
#include<iostream>
#include<math.h>
#include<bits/stdc++.h>
#include<cmath>
#define ll long long int
#define hell 1000000007LL
using namespace std;
ll power(ll x, ll y,ll z){
    
    if(y==0)
     return 1;
    else
    {
        ll p=power(x,y/2,z);
        ll w=(p*p)%z;
        if(y%2==0)
         return w;
        else
        return (x*w)%z;
    }}
ll gcd(ll x,ll y)
{
    if(y==0)
     return x;
    else
    return gcd(y,x%y);}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(20);
   ll n;
   cin>>n;
   ll a[n],s=0;
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
       s=s+a[i];
   }
   bool f[n+1][s+1];
   for (int i = 0; i <= n; i++)
        f[i][0] = true;
    for (int i = 1; i <= s; i++)
        f[0][i] = false;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= s; j++) {
            if (j < a[i - 1])
                f[i][j] = f[i - 1][j];
            if (j >= a[i - 1])
                f[i][j] = f[i - 1][j]
                               || f[i - 1][j - a[i - 1]];
        }
    }
    int b[100001];
    ll m=s;
    for(int i=1;i<s;i++)
    {
        int c=0;
        for(int j=0;j<n+1;j++)
        {
            if(f[j][i]==true){
            c++;
            break;}
        }
        if(c)
        b[i]=1;
    }
    for(ll i=1;i<s;i++)
    {
        if(b[i]==1)
        {
            ll x=i;
            if(x<s-i)
            x=s-i;
            m=min(m,x);
        }
    }
    cout<<m;}
    