μονευ

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
long long y=0;
vector<long long> q;
bool 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(K[n][W] == W){
            int res = K[n][W];
    w = W;
    for (i = n; i > 0 && res > 0; i--) {
        if (res == K[i - 1][w])
            continue;
        else {
            q.push_back(val[i-1]);
            res = res - val[i - 1];
            w = w - val[i - 1];
        }
    }
        return true;
    }
    else if(W == 0){
            return true;
    }
    else{
        return false;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long n;
    scanf("%lld",&n);
    long long val[n];
    long long x;
    vector<long long>k;
    vector<long long>q1;
    long long temp;
    for(long long i=0;i<n;i++){
        scanf("%lld",&val[i]);
        y+=val[i];
    }
    int tr;
    tr = y/2;
    bool b=true;
    while(tr > 0){
        temp = y - (2 * tr);
        b = printknapSack(temp,val,n,y);
            if(b == true){
                    if(temp != 0){
                            while(!q.empty()){
                               for(int i=0;i<n;i++){
                                    if(val[i] == q.back()){
                                        val[i] = 0;
                                        k.push_back(i);
                                        q1.push_back(q.back());
                                        q.pop_back();
                                        break;
                                    }
                                }
                            }
                        }
                b = printknapSack(tr,val,n,y);
                if(temp != 0){
                    while(!k.empty()){
                        val[k.back()] = q1.back();
                        k.pop_back();
                        q1.pop_back();
                    }
                }
                if(b == 1){
                    break;
                }
                tr--;
            }
            else{
               tr--;
            }
    }
    if(tr == 0){
        printf("%lld",y);
    }
    else{
        printf("%lld",tr+temp);
    }
    return 0;
}