#include<bits/stdc++.h>
using namespace std;
#define N 16
typedef long long ll;
inline void ckmin(int &x,int y){x=min(x,y);}
const int inf=0x3f3f3f3f;
int n,a[N];
int dp[1<<N];
bool check(int lim){
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=0;i<(1<<n);++i){
		if(dp[i]==inf)continue;
		for(int j=0;j<n;++j){
			if(!(i>>j&1)){
				if(dp[i]+a[j]<=lim){
					ckmin(dp[i|(1<<j)],max(0,dp[i]+a[j]));
				}
			}
		}
	}
	return dp[(1<<n)-1]<inf;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	int mx=-inf;
	for(int i=0;i<n;++i){
		cin>>a[i];
		mx=max(mx,a[i]);
	}
	if(mx<=0){
		cout<<mx<<'\n';
		return 0;
	}
	int l=0,r=2e6,ans=r;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid;
			ans=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<ans<<'\n';
	return 0;
}