#include <bits/stdc++.h>
 
using namespace std;

#define ld long double
#define ll long long
#define FF first.first
#define FS first.second
#define SF second.first
#define SS second.second
#define PB push_back
#define MP make_pair
#define all(cont) cont.begin(),cont.end()
#define rall(cont) cont.rbegin(), cont.rend()
#define FOR(i, j) for(int i=0;i<j;i++)
#define RFOR(i, j) for (int i=j;i>=0;i--)
#define GO cin.tie(NULL);
#define FAST ios_base::sync_with_stdio(false);
typedef pair<int,int> pii;



// Your function
//DEBBUGGING STUFF, JUST USE deb(a,b,c) and it will print the variables;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cout << vars << " = ";
    string delim = "";
    (..., (cout << delim << values, delim = ", "));
    cout<<endl;

}

const int maxn=1e5+10;
int main(){
    GO FAST;
    int n;cin>>n;
    bitset<maxn> possiveis(0);
    possiveis.set(0);
    int soma=0;
    FOR(i,n){
        int a;
        cin>>a;
        soma+=a;
        auto cop=possiveis;
        cop<<=a;
        possiveis|=cop;
    }
    int ans=soma;
    FOR(i,maxn){
        if (possiveis[i]){
            ans=min(max(i,soma-i),ans);
        }
    }
    cout<<ans<<'\n';

}
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<stdio.h>
#include<algorithm>
constexpr long long MOD = 998244353;
constexpr long long MOD32 = 665496236;
    char f[5000][5000];
    long long dp[5000];

int main(){
    long H=0, W=0, K=0;
    char c=getchar_unlocked();
    while(c<='9'&&c>='0') {H=(H<<1)+(H<<3)+c-'0'; c=getchar_unlocked();}
    c=getchar_unlocked();
    while(c<='9'&&c>='0') {W=(W<<1)+(W<<3)+c-'0'; c=getchar_unlocked();}
    c=getchar_unlocked();
    while(c<='9'&&c>='0') {K=(K<<1)+(K<<3)+c-'0'; c=getchar_unlocked();}

    long long y = H * W - K;
    while(--K>=0){
        long h=0, w=0;
        c=getchar_unlocked();
        while(c<='9'&&c>='0') {h=(h<<1)+(h<<3)+c-'0'; c=getchar_unlocked();}
        c=getchar_unlocked();
        while(c<='9'&&c>='0') {w=(w<<1)+(w<<3)+c-'0'; c=getchar_unlocked();}
        f[h-1][w-1] = getchar_unlocked();
        getchar_unlocked();
    }
    --H; --W;
    dp[0] = 1;
    for(int i = 0; i < H; ++i){
        for (int j = 0; j < W; ++j){
            switch(f[i][j]) {
                case 'R':
                    dp[j + 1] += dp[j];
                    dp[j] = 0;
                    break;
                case '\0':
                    dp[j] = dp[j] * MOD32 % MOD;
                case 'X':
                    dp[j + 1] += dp[j];
            }
        }
            switch(f[i][W]) {
                case 'R':
                    dp[W] = 0;
                    break;
                case '\0':
                    dp[W] = dp[W] * MOD32 % MOD;
            }
    }
    for (int j = 0; j < W; ++j){
        switch(f[H][j]) {
            case '\0':
                dp[j] = dp[j] * MOD32 % MOD;
            case 'R':
            case 'X':
                dp[j + 1] += dp[j];
        }
    }

    long long ans = dp[W] % MOD;
    long long x = 3;
    while(y) {
      if(y & 1) ans = ans * x % MOD;
      x = x * x % MOD;
      y >>= 1;
    }
    printf("%d", ans);

    return 0;
}

