#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define ar3 array <int , 3>
using namespace std;
const int INF = 1e9 + 7;
const int maxn = 2e5 + 7;
const int maxx = 1e5;
int n , a[501] , dp[501][100001] , sum = 0;
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sum = accumulate(a+1 , a+n+1 , 0);
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= maxx; j++) dp[i][j] = -INF;
}
dp[0][0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= maxx; j++)
{
dp[i][j] = max(dp[i][j] , dp[i-1][j]);
if(j + a[i] <= maxx)
{
dp[i][j + a[i]] = max(dp[i][j + a[i]] , dp[i-1][j] + a[i]);
}
int diff = abs(dp[i-1][j] - (dp[i-1][j] - j + a[i]));
if(diff > maxx) continue;
if(dp[i-1][j] - j + a[i] >= dp[i-1][j])
{
dp[i][diff] = max(dp[i][diff] , dp[i-1][j] - j + a[i]);
}
else
{
dp[i][diff] = max(dp[i][diff] , dp[i-1][j]);
}
}
}
cout << sum - dp[n][0] << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
