#include<bits/stdc++.h>
using namespace std;
int n,a[55],as,dp[28][1000005],f[28][1000005];
inline void dfs(int x,int y,int s,int ss){
    if(dp[x][s+500000]>=ss) return;
    dp[x][s+500000]=ss;
    if(x>y) return;
    dfs(x+1,y,s+a[x],ss+a[x]);
    dfs(x+1,y,s-a[x],ss+a[x]);
    dfs(x+1,y,s,ss);
    return;
}
inline void dfs2(int x,int y,int s,int ss){
    if(x>y){
        as=max(as,dp[n/2+1][s+500000]+ss);
        return;
    }
    if(f[x-n/2][s+500000]>=ss) return;
    f[x-n/2][s+500000]=ss;
    if(x>y) return;
    dfs2(x+1,y,s-a[x],ss+a[x]);
    dfs2(x+1,y,s+a[x],ss+a[x]);
    dfs2(x+1,y,s,ss);
    return; 
}
int main(){
    freopen("cookie.in","r",stdin);
    freopen("cookie.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=n/2+1;i++){
        for(int j=0;j<=1000000;j++) dp[i][j]=f[i][j]=-1e9;
    }
    dfs(1,n/2,0,0);
    dfs2(n/2+1,n,0,0);
    cout<<as/2;
    return 0;
}