///https://agc020.contest.atcoder.jp/tasks/agc020_c?lang=en

#include<bits/stdc++.h>
#define i64 long long
#define inf 1000000000000000000
using namespace std;

int ara[2009];
int main()
{
    int n;
    scanf("%d",&n);

    int sum=0,mx=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&ara[i]);
        sum+=ara[i];
        mx=max(mx,ara[i]);
    }


    int avg=sum/n , last=mx*n;


    bitset<4000009>bset[n+5];


    for(int i=0;i+ara[1]<=last;i++)
    {
        bset[1][i+ara[1]]=1;
    }


    for(int i=2;i<=n;i++)
    {
        bset[i]=bset[i-1]|(bset[i-1]<<ara[i]);
    }

    for(int i=min(avg+1,last);i<=last;i++)
    {
        if(bset[n][i]==1)
        {
            printf("%d\n",i);
            return 0;
        }
    }


    return 0;
}
