#include<bits/stdc++.h>
#define ll long long int
#define nl "\n"
#define vec vector<ll>
#define pb push_back
#define MOD 1000000007
#define test ll testc;cin>>testc;while(testc--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
ll bpow(ll a,ll b) {ll ans=1;while (b>0){if (b&1) ans=(ans*a)%MOD;b/=2;a=(a*a)%MOD;}return ans;}
int main()
{
	#ifndef ONLINE_JUDGE
    	freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
    	#endif
    	fast
    	{
    		ll n; cin>>n;
    		ll a[n];
    		ll t=0;
    		for(int i=0;i<n;i++)
    		{
    			cin>>a[i];
    			t+=a[i];
    		}
    		ll x[100000+1]={0};
    		x[0]=1;
    		for (int i=0;i<n;i++)
    		{
    			for (int j=100000;j>=0;j--)
    			{
    				if (x[j]>0) x[j+a[i]]=1;
    			}
    		}
    		for (int i=0;i<=100000;i++)
    		{
    			if (i>=(t+1)/2 and x[i]>0)
    			{
    				cout<<i<<nl;
    				break;
    			}
    		}
    	}
    	
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INCANT cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(12)
const int INF = 1e9 + 7;
const ll LINF = 1e18 + 7;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
void debug_out();
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T);
#ifdef MY_DEBUG
#define dbg(...) debug_out(__VA_ARGS__)
#define dbgs(x) cout << "\033[33m" << x << "\033[m"　<< " "
#define dbge cout << endl
#else
#define dbg(...)
#define dbgs(x)
#define dbge
#endif
template <class T> bool chmax(T &, const T &);
template <class T> bool chmin(T &, const T &);
template <class T> T pwr(T, ll);
template <class T> T squ(T);
ll fact(ll);
ll comb(ll, ll);

int main() {
    INCANT;
    int n;
    cin >> n;
    vector<int> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];

    vector<vector<bool>> dp(n, vector<bool>(110000, false));
    dp[0][0] = true, dp[0][t[0]] = true;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 110000; j++) {
            if (dp[i - 1][j] == true) {
                dp[i][j + t[i]] = true;
                dp[i][j] = true;
            }
        }
    }

    int ans = INF;
    int sum = accumulate(t.begin(), t.end(), 0);
    for (int i = 0; i < 110000; i++) {
        if (dp[n-1][i] == true) chmin(ans, max(i, sum-i));
    }

    cout << ans << endl;
}

/*





















-----------------------------------MY_FUNCTION------------------------------------ */

void debug_out() {
    cout << endl;
}

template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
    cout << "\033[33m" << H << "\033[m"
         << " ";
    debug_out(T...);
}

template <class T> bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T> bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template <class T> T pwr(T x, ll n) {
    T ans = 1;
    for (int i = 0; i < n; i++) {
        ans *= x;
    }
    return ans;
}

template <class T> T squ(T x) {
    return x * x;
}

ll fact(ll n) {
    ll res = 1;
    for (ll i = 1; i <= n; i++) res *= i;
    return res;
}

ll comb(ll n, ll r) {  // comb(60, 30)までオーバーフローなし
    ll res = 1;
    for (int i = 1; i <= r; i++) {
        res *= n--;
        res /= i;
    }
    return res;
}
