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

const int V = 1e6 + 5;
const int base = 5e5;
const int N = 55;

int n;
int f[V],g[V];

signed main()
{
    freopen("cookie.in","r",stdin);
    freopen("cookie.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    memset(f,-0x3f,sizeof(f));
    memset(g,-0x3f,sizeof(g));
    g[base] = 0;
    for(int i = 1;i <= n;i++){
        int x;cin>>x;
        for(int j = 0;j <= V - 5;j++) if(j + x <= V - 5) f[j + x] = max(f[j + x],g[j] + x);
        for(int j = 0;j <= V - 5;j++) if(j - x >= 0) f[j - x] = max(f[j - x],g[j]);
        for(int j = 0;j <= V - 5;j++) g[j] = f[j];
    }
    
    cout<<f[base]<<'\n';
    
    return 0;
 }