#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <cmath>


long long FindCentral(std::vector<std::vector<long long>> &A, long long K, long long si, long long sj, std::vector<long long> &AK)
{
    long long index = 0;
    
    for(long long i = si; i < (si + K); i++){
        for(long long j = sj; j < (sj + K); j++){
            AK[index] = A[j][i];
            index++;
        }
    }
    
    std::sort(AK.begin(), AK.end());
    //std::cout << AK[(K*K)/2 -1] << std::endl;

    long long t  = 0;
    if((((K*K)) % 2) == 0){
        t = -1;
    }

    return AK[(K*K)/2 + t];
} 


long long FindCentral2(std::vector<std::vector<long long>> &A, long long K, long long si, long long sj, std::vector<long long> &AK, long long & index)
{
    for(long long j = sj; j < (sj + K); j++){
            AK[index] = A[j][si];
            index++;

            if(index == K*K){
                index = 0;
            }
    }

    
    std::sort(AK.begin(), AK.end());

    for(long long i = 0 ; i < K*K; i++){
        std::cout << AK[i] << " ";
    }
    long long t  = 0;
    if((((K*K)) % 2) == 0){
        t = -1;
    }

    std::cout << AK[(K*K)/2 + t] << std::endl;

    return AK[(K*K)/2 + t];
} 

long long find_max_dp(long long N, std::vector<long long> &num_list, long long MAX_NUM) {
    int tmp_choice, tmp_not_choice;
    std::vector<std::vector<long long>> table(N, std::vector<long long>(MAX_NUM+1, 0));
 
    // DP表の一番上（i = 0）を初期化
    for(int j = 0; j <= MAX_NUM; j += 1) {
        if(num_list[0] > j) {
            table[0][j] = 0; // 何も入れられないとき
        }
        else {
            table[0][j] = num_list[0]; // 0番目の数字を足せるとき
        }
    }
 
    for(int i = 1; i < N; i += 1) {
        for(int j = 0; j <= MAX_NUM; j += 1) {
            tmp_not_choice = table[i-1][j];
            if(num_list[i] > j) {
                table[i][j] = tmp_not_choice;
            }
            else {
                tmp_choice = table[i-1][j - num_list[i]] + num_list[i];
                if(tmp_choice >= table[i-1][j])
                    table[i][j] = tmp_choice;
                else
                    table[i][j] = tmp_not_choice;
            }
        }
    }
 
    return table[N-1][MAX_NUM];
}

int main()
{
    long long N;
    
    std::cin >> N;
    long long Tsum = 0;
    std::vector<long long> T(1001, 0);
    std::vector<long long> T2(N, 0);

    for(long long i = 0; i < N; i++){
        long long temp;
        std::cin >> temp;
        T2[i] = temp;
        Tsum += temp;
        T[temp]++;
    }
    std::sort(T2.begin(), T2.end());

    long long ans = find_max_dp(N, T2, Tsum/2);

    ans = Tsum - ans;
   
    std::cout << ans << std::endl;
    return 0;
}
  
#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=110;
int n;
int a[N];
bool dp[N][N*2000];
int sum=0;
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	forn(i,1,n)cin>>a[i];
	forn(i,1,n)sum+=a[i];
	dp[0][100000]=1;
	forn(i,1,n){
		rep(j,200001){
			if(dp[i-1][j]){
				dp[i][j+a[i]]=dp[i][j-a[i]]=1;
			}
		}
	}
	forn(d,0,100000){
		if(dp[n][100000+d]||dp[n][100000-d]){
			cout<<(sum+d)/2;
			return 0;
		}
	}
	return 0;
}
