money

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