μονευ.ψππ

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