#include<bits/stdc++.h>
#define ll long long
#define debug cout<<"?\n";
using namespace std;
const int N=60;
const int M=5e5+10;
const int NINF=-1e9;
int n,a[N],ans=0,dp[2*M],ndp[2*M],tmp[2*M],sum=0,s;
int main()
{
    freopen("cookie.in","r",stdin);
    freopen("cookie.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    s=2*sum;
    for(int i=0;i<=s;i++) dp[i]=NINF;
    dp[sum]=0;
    for(int i=1;i<=n;i++){
        for(int k=0;k<=s;k++) ndp[k]=dp[k];
        for(int k=0;k<=s;k++){
            if(dp[k]<0) continue;
            if(k+a[i]>=0&&k+a[i]<=s){
                int idx1=k+a[i];
                if(ndp[idx1]<dp[k]+a[i]) ndp[idx1]=dp[k]+a[i];
            }
            if(k-a[i]>=0&&k-a[i]<=s){
                int idx2=k-a[i];
                if(ndp[idx2]<dp[k]) ndp[idx2]=dp[k];
            }
        }
        for(int k=0;k<=s;k++) swap(dp[k],ndp[k]);
    }
    ans=dp[sum];
    cout<<ans<<'\n';
    return 0;
}