#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 55;
const int Maxn = 500010;

int n;
int nums[N];
int sum;
int dp[N][3][(Maxn << 1) + 10]; // 0: Francin 1: Nilly 2: Mom

int main () {
	
	freopen ("cookie.in", "r", stdin);
	freopen ("cookie.out", "w", stdout);
	
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf ("%d", &(nums[i]));
		sum += nums[i];
	}
	
	for (int i = 0; i <= n; i++) {
		for (int opt = 0; opt < 3; opt++) {
			for (int bigger = -sum; bigger <= sum; bigger++) {
				dp[i][opt][bigger + Maxn] = -1e9;
			}
		}	
	}
	dp[0][0][Maxn] = dp[0][1][Maxn] = dp[0][2][Maxn] = 0;
	for (int i = 1; i <= n; i++) {
		for (int opt = 0; opt < 3; opt++) {
			for (int bigger = -sum; bigger <= sum; bigger++) {
				// Francine:
				if (bigger + nums[i] <= sum) {
					dp[i][0][bigger + nums[i] + Maxn] = 
					max (dp[i][0][bigger + nums[i] + Maxn], dp[i - 1][opt][bigger + Maxn] + nums[i]);
				}
				
				// Nilly:
				if (bigger - nums[i] >= -sum) {
					dp[i][1][bigger - nums[i] + Maxn] =
					max (dp[i][1][bigger - nums[i] + Maxn], dp[i - 1][opt][bigger + Maxn]);
				}
				
				// Mom:
				dp[i][2][bigger + Maxn] = max (dp[i][2][bigger + Maxn], dp[i - 1][opt][bigger + Maxn]);
			}
		}
	}
	
//	for (int i = 1; i <= n; i++) {
//		cout << i << " id" << endl;
//		for (int opt = 0; opt < 3; opt++) {
//			cout << opt << " opt" << endl;
//			for (int bigger = -sum; bigger <= sum; bigger++) {
//				cout << bigger << " : " << dp[i][opt][bigger + Maxn] << endl;
//			}
//		}
//	}
	
	cout << max ({dp[n][0][Maxn], dp[n][1][Maxn], dp[n][2][Maxn]}) << endl;
	
	return 0;
}