#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
#include<functional>
using namespace std;
#define rep(i,a,n) for(ll i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define Pll pair<llint,llint>
#define keta(a)  fixed << setprecision(a)
const ll mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
const ll INF = 1000;

class UnionFind {
public:
	//親の番号を格納する
	vector<int> par;

	//最初は全てが根であるとして初期化
	UnionFind(int N) {
		par.resize(N);
		for (int i = 0; i < N; i++)par[i] = i;
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (par[A] == A) return A;
		return par[A] = root(par[A]);
	}


	//AとBをくっ付ける
	bool unite(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//Bの親をAに変更する
		par[B] = A;

		return true;
	}
	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

template<class T>
class SegTree {
public:
	T size;
	vector<T> seg; //配列
	T e; //単位元
	function <T(T, T)> f; //演算
	function<T(T, T)> updata; //更新
	SegTree(T n, T _e, function<T(T, T)> _f, function<T(T, T)> _updata) { //コンストラクタ(初期化)
		f = _f;
		e = _e;
		updata = _updata;
		size = 1;
		while (size < n)size *= 2;
		seg.resize(size * 2 - 1, e);
	}

	void change(T n, T k) { //一点更新
		n += size - 1;
		seg[n] = updata(seg[n], k);
		while (n > 0) {
			n = (n - 1) / 2;
			seg[n] = f(seg[n * 2 + 1], seg[n * 2 + 2]);
		}
	}
	T query(T a, T b, T l, T r, T k) {
		if (b <= l || r <= a)return e;
		if (a <= l && r <= b)return seg[k];
		T v1 = query(a, b, l, (l + r) / 2, k * 2 + 1);
		T v2 = query(a, b, (l + r) / 2, r, k * 2 + 2);
		return f(v1, v2);
	}

};


long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//aCbをmod.mで割った余りを求める
llint C(llint n, llint r, llint m) {
	llint ans = 1;
	for (llint i = 0; i < r; i++) {
		ans *= n - i;
		ans %= m;
	}
	for (llint i = 1; i <= r; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}

llint gcd(llint a, llint b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
int main(){
	ll n;
	cin >> n;
	hei(ll) a;
	for (ll i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			a.push_back(i);
			if ((n / i) == i)continue;
			a.push_back(n / i);
		}
	}
	sort(a.begin(), a.end());
	rep(i, 0, a.size())cout << a[i] << endl;
	return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,k,n) for(int i = k;i < (n);i++)
const int INF = 1e9;
template <class T> inline bool chmin(T &a, T b) {if (a > b) {a = b; return true;} return false;}

int main(void){
    int n,sum = 0,ans = INF;
    cin >> n;
    vector<int> t(n);
    rep(i, n) cin >> t[i],sum += t[i];
    vector<vector<bool>> dp(n+1,vector<bool>(sum+1));
    dp[0][0] = true;

    rep2(i,1,n+1){
        rep(j,sum+1){
            if(j >= t[i]) dp[i][j] = dp[i-1][j] | dp[i-1][j-t[i]];
            else dp[i][j] = dp[i-1][j];
        }
    }

    rep(i,sum+1) if(dp[n][i]){
        chmin(ans,(int)max(i,sum-i));
    }

    cout << ans << endl;

    return 0;
}