#include <iostream>
#include <algorithm>
using namespace std;
int MAX=20000;
//jakos dziala ale nie zwraca optimum z ilus tam przypadkow
/*int szukaj_min(int N, int tab[], int znak_startu)
{
tab[0]*=znak_startu;
int min=tab[0]; //zawiera kolejne wart_predk
for(int i=0;i<N-1;i++) //szuka minimum
{
if(abs(min-tab[i+1]) >= abs(min+tab[i+1]))
tab[i+1]*=1;
else tab[i+1]*=-1;
min=min+tab[i+1]; //policz akt predkosc
}
return abs(min);
}
*/
void wyp_tab(int **tab, int w, int k)
{
for (int i=0;i<w;i++)
{
for (int j=0;j<k;j++)
{tab[i][j]=MAX;}
}
}
/*void wys_tab(int **tab, int w, int k)
{
for (int i=0;i<w;i++)
{
for (int j=0;j<k;j++)
cout<<tab[i][j]<<" ";
cout<<endl;
}
}
*/
int knapsack_mod(int N, int *W, int p)
{
int min_lokal=MAX;
int **V=new int*[N];
for(int i=0; i<N; i++)
V[i] = new int[p];
wyp_tab(V,N,p);
V[0][W[0]]=W[0];
for (int i=0; i<N-1; i++)
{
for (int w=0; w<p; w++)
{
if(V[i][w]!=MAX)
{
int wart_1=V[i][w]+W[i+1];
if(V[i][w]+W[i]<=p)
V[i+1][wart_1]=wart_1;
int wart_2=abs(V[i][w]-W[i+1]);
V[i+1][wart_2]=wart_2;
}
}
}
for (int i=0; i<p; i++)
{
if(V[N-1][i]<min_lokal)
min_lokal=V[N-1][i];
}
for(int i=0; i<N; i++)
{delete [] V[i];}
delete [] V;
return min_lokal;
}
int main()
{
int t=0; //ilosc testów
int N=0; //ilosc pomiarow
cin>>t;
for (int j=0; j<t; j++)
{
int *tab, plecak;
int min_w=MAX;
int max_w=0, max_ww=0;
cin>>N;
tab= new int[N];
for(int k=0;k<N;k++) //zwroci max przy okazji
{cin>>tab[k]; max_w+=tab[k];}
sort(tab, tab+N, greater <int>() );
max_ww=max_w;
if (max_w%2!=0)
{max_ww=max_w+1;}
plecak=max(max_ww,tab[0]);
min_w=knapsack_mod(N,tab,plecak);
cout<<endl<<min_w<<" "<<max_w<<endl;
delete [] tab;
}
//system("pause");
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgTUFYPTIwMDAwOwoKLy9qYWtvcyBkemlhbGEgYWxlIG5pZSB6d3JhY2Egb3B0aW11bSB6IGlsdXMgdGFtIHByenlwYWRrb3cKLyppbnQgc3p1a2FqX21pbihpbnQgTiwgaW50IHRhYltdLCBpbnQgem5ha19zdGFydHUpCnsKICAgIHRhYlswXSo9em5ha19zdGFydHU7CiAgICBpbnQgbWluPXRhYlswXTsgICAgICAgICAgICAgICAgICAgICAvL3phd2llcmEga29sZWpuZSB3YXJ0X3ByZWRrCiAgICBmb3IoaW50IGk9MDtpPE4tMTtpKyspICAgICAgICAgICAgICAvL3N6dWthIG1pbmltdW0KICAgICAgICB7CiAgICAgICAgaWYoYWJzKG1pbi10YWJbaSsxXSkgPj0gYWJzKG1pbit0YWJbaSsxXSkpCiAgICAgICAgICAgIHRhYltpKzFdKj0xOwogICAgICAgICAgICBlbHNlIHRhYltpKzFdKj0tMTsKICAgICAgICBtaW49bWluK3RhYltpKzFdOyAgICAgICAgICAgICAgICAgIC8vcG9saWN6IGFrdCBwcmVka29zYwogICAgICAgIH0KICAgIHJldHVybiBhYnMobWluKTsKfQoqLwogCnZvaWQgd3lwX3RhYihpbnQgKip0YWIsIGludCB3LCBpbnQgaykKewogICAgZm9yIChpbnQgaT0wO2k8dztpKyspCiAgICAgICAgewogICAgICAgIGZvciAoaW50IGo9MDtqPGs7aisrKQogICAgICAgICAgICB7dGFiW2ldW2pdPU1BWDt9CiAgICAgICAgfQp9Ci8qdm9pZCB3eXNfdGFiKGludCAqKnRhYiwgaW50IHcsIGludCBrKQp7CiAgICBmb3IgKGludCBpPTA7aTx3O2krKykKICAgIHsKICAgICAgICBmb3IgKGludCBqPTA7ajxrO2orKykKICAgICAgICAgICAgY291dDw8dGFiW2ldW2pdPDwiICAgICI7CiAgICAgICAgY291dDw8ZW5kbDsKICAgIH0KfQoqLwoKaW50IGtuYXBzYWNrX21vZChpbnQgTiwgaW50ICpXLCBpbnQgcCkKewogICAgaW50IG1pbl9sb2thbD1NQVg7CiAgICBpbnQgKipWPW5ldyBpbnQqW05dOwogICAgZm9yKGludCBpPTA7IGk8TjsgaSsrKQogICAgICAgIFZbaV0gPSBuZXcgaW50W3BdOwogICAgd3lwX3RhYihWLE4scCk7CiAgICBWWzBdW1dbMF1dPVdbMF07CiAgICBmb3IgKGludCBpPTA7IGk8Ti0xOyBpKyspCiAgICAgICAgewogICAgICAgIGZvciAoaW50IHc9MDsgdzxwOyB3KyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgaWYoVltpXVt3XSE9TUFYKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IHdhcnRfMT1WW2ldW3ddK1dbaSsxXTsKICAgICAgICAgICAgICAgIGlmKFZbaV1bd10rV1tpXTw9cCkKICAgICAgICAgICAgICAgICAgICBWW2krMV1bd2FydF8xXT13YXJ0XzE7CiAgICAgICAgICAgICAgICBpbnQgd2FydF8yPWFicyhWW2ldW3ddLVdbaSsxXSk7CiAgICAgICAgICAgICAgICBWW2krMV1bd2FydF8yXT13YXJ0XzI7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICBmb3IgKGludCBpPTA7IGk8cDsgaSsrKQogICAgICAgIHsKICAgICAgICBpZihWW04tMV1baV08bWluX2xva2FsKQogICAgICAgICAgICBtaW5fbG9rYWw9VltOLTFdW2ldOwogICAgICAgIH0KICAgIGZvcihpbnQgaT0wOyBpPE47IGkrKykKICAgICAgICB7ZGVsZXRlIFtdIFZbaV07fQogICAgZGVsZXRlIFtdIFY7CiAgICByZXR1cm4gbWluX2xva2FsOwp9CgppbnQgbWFpbigpCnsKICAgIGludCB0PTA7IC8vaWxvc2MgdGVzdMOzdwogICAgaW50IE49MDsgLy9pbG9zYyBwb21pYXJvdwogICAgY2luPj50OwogICAgZm9yIChpbnQgaj0wOyBqPHQ7IGorKykKICAgICAgICB7CiAgICAgICAgaW50ICp0YWIsIHBsZWNhazsKICAgICAgICBpbnQgbWluX3c9TUFYOwogICAgICAgIGludCBtYXhfdz0wLCBtYXhfd3c9MDsKICAgICAgICBjaW4+Pk47CiAgICAgICAgdGFiPSBuZXcgaW50W05dOwogICAgICAgIGZvcihpbnQgaz0wO2s8TjtrKyspICAgICAgICAgICAgICAgIC8vendyb2NpIG1heCBwcnp5IG9rYXpqaQogICAgICAgICAgICB7Y2luPj50YWJba107IG1heF93Kz10YWJba107fQogICAgICAgIHNvcnQodGFiLCB0YWIrTiwgZ3JlYXRlciA8aW50PigpICk7CiAgICAgICAgbWF4X3d3PW1heF93OwogICAgICAgIGlmIChtYXhfdyUyIT0wKQogICAgICAgICAgICB7bWF4X3d3PW1heF93KzE7fQogICAgICAgIHBsZWNhaz1tYXgobWF4X3d3LHRhYlswXSk7CiAgICAgICAgbWluX3c9a25hcHNhY2tfbW9kKE4sdGFiLHBsZWNhayk7CiAgICAgICAgY291dDw8ZW5kbDw8bWluX3c8PCIgIjw8bWF4X3c8PGVuZGw7CiAgICAgICAgZGVsZXRlIFtdIHRhYjsKICAgICAgICB9CiAgICAvL3N5c3RlbSgicGF1c2UiKTsKICAgIHJldHVybiAwOwp9