moneyc++

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
long long printknapSack(long long W, long long val[], long long n,long long y){
    long long i, w;
    long long x=0;
    bool K[n + 1][W + 1];
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
                K[i][w] =0;
            if (i == 0 && w == 0){
                K[i][w] = 1;
            }
            else if( w >= val[i]){
                K[n][w] = max(K[i-1][w],K[i-1][w-val[i]]);
            }
        }
    }
    if(W % 2 == 1){
        W--;
    }
    while(K[n][W] == 0 || K[n][W/2] == 0){
            W-=2;
    }
    return W;
}
int main(){
    long long n;
    cin>>n;
    long long val[n];
    long long y=0;
    long long x;
    for(long long i=0;i<n;i++){
        cin>>val[i];
        y+=val[i];
    }
    int tr;
        tr = printknapSack(y,val,n,y);
    if(tr == y){
        cout<<tr/2;
    }
    else{
        cout<<(tr/2)+(y - tr);
    }
    return 0;
}