money

#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;
    long long K[n + 1][W + 1];
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0){
                K[i][w] = 0;
            }
            else if (val[i - 1] <= w){
                K[i][w] = max(val[i - 1] +K[i - 1][w - val[i - 1]], K[i - 1][w]);
            }
            else{
                K[i][w] = K[i - 1][w];
            }
        }
    }
    if(W % 2 == 1){
        W--;
    }
    while(K[n][W] != K[n][W/2] * 2){
            W-=2;
    }
    return K[n][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;
}