#include<bits/stdc++.h>
#define pb push_back
#define int long long int
#define INF 1e18
#define vec vector<int>
#define REP(i,a,b) for(i=a;i<b;i++)
using namespace std;
int dp[81][6001][20][3];
int q;
int ans(int a[],int n,int p,int st,int x)
{
  if(n>q)
        return 0;
  if(dp[n][p][st][x]!=-1)
            return dp[n][p][st][x];
  if(p>=a[n] && st>0 && x==2)
        return dp[n][p][st][x]=max(a[n]+ans(a,n,p+a[n],st-1,0),max(ans(a,n,p-a[n],st+1,1)-a[n],ans(a,n+1,p,st,2)));
  else if(p>=a[n] && x!=0)
        return dp[n][p][st][x]=max(ans(a,n,p-a[n],st+1,1)-a[n],ans(a,n+1,p,st,2));
  else if(st>0 && x!=1)
        return dp[n][p][st][x]=max(a[n]+ans(a,n,p+a[n],st-1,0),ans(a,n+1,p,st,2));
  else
        return dp[n][p][st][x]=ans(a,n+1,p,st,2);
}
main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  memset(dp,-1,sizeof(dp));
  int n;
  cin>>n;
  q=n;
  int a[n+1],i;
  for(i=1;i<=n;i++)
    cin>>a[i];
  int p=1000,st=0;
  cout<<ans(a,1,p,st,2)+1000;
}