PangPu

#include<stdio.h>
int n;
int arr[1010];
int max(int a,int b){
    return (a > b ? a : b);
}
//int maxa = -2e9;
/*
int cal(int index,int sum){
    if(index > n){
//      maxa = max(sum,maxa);
        return sum;
    }
//  printf("Test %d %d\n",index,sum);
    int choose = sum + arr[index];
    if(choose < -30000)choose += 60001;
    if(choose > 30000)choose -= 60001;
    int notchoose = sum;
//  if(notchoose < -30000)notchoose += 60001;
//  if(notchoose > 30000)notchoose -= 60001;
    return max(cal(index+1,choose),cal(index+1,notchoose));
}
*/
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
    }
//  cal(1,0);
//  printf("%d",maxa);
//  printf("%d\n",cal(1,0));

    int dp[2][60010];
    for(int i = 0 ; i < 60010 ; i ++){
        dp[(n+1)%2][i] = i - 30000;
    }
    for(int i = n ; i >= 1 ; i --){
        for(int sum = -30000 ; sum <= 30000 ; sum ++ ){
            int choose = sum + arr[i];
            if(choose < -30000)choose += 60001;
            if(choose > 30000)choose -= 60001;
            int notchoose = sum;
        //  if(notchoose < -30000)notchoose += 60001;
        //  if(notchoose > 30000)notchoose -= 60001;
            dp[i%2][sum+30000] = max(dp[(i+1)%2][choose + 30000],dp[(i+1)%2][notchoose + 30000]);
        }
    }
    printf("%d",dp[1][30000]);
    return 0;
}