bete2

#include <fstream>
#include <cstring>
using namespace std;
int q,n,x,t,s,c[101],dp[1000001];

int main()
{
    ifstream f("bete.in");
    f>>q;
    ofstream g("bete.out");
    while(q--)
    {
        s=0;
        f>>n;
        memset(c,0,sizeof(c));
        while(n--)
            f>>x,++c[x],s+=x;
        t=s/2;
        memset(dp,0,(t+1)*4);
        dp[0]=1;
        for(int x=1;x<101;++x)
        {
            for(;c[x];c[x]/=2)
            {
                int y=(c[x]+1)/2*x;
                for(int i=t-y;i>=0;--i)
                    dp[i+y]|=dp[i];
            }
        }
        while(!dp[t])
        --t;
        g<<s-2*t<<'\n';
    }
    f.close();
    g.close();
    return 0;
}