[cpp]
#include
#include
#define maxsize 4010
#define size 2000
int dp[110][maxsize];
int max2(int a,int b)
{
return a>b a:b;
}
int max(int a,int b,int c)
{
return max2(a,b)>c max2(a,b):c;
}
int a[1010];
int main()
{
int t,n,num,i,j,zero;
scanf("%d",&t);
for(num=1;num<=t;num++)
{
zero=0;
scanf("%d",&n);
j=1;
for(i=1;i<=n;i++)
{
scanf("%d",&a[j++]);
if(a[j-1]==0)
{
zero=1;
j--;
}
}
n=j-1;
for(i=0;i<110;i++)
for(j=0;j
dp[i][j]=INT_MIN;
dp[0][size]=0;
for(i=1;i<=n;i++)
for(j=0;j
if(j-a[i]>=0&&j+a[i]
dp[i][j]=max(dp[i-1][j-a[i]]+a[i],dp[i-1][j+a[i]]+a[i],dp[i-1][j]);
else
{
if(j-a[i]<0&&j+a[i]
dp[i][j]=max2(dp[i-1][j+a[i]]+a[i],dp[i-1][j]);
else
if(j+a[i]>=maxsize&&j-a[i]>=0)
dp[i][j]=max2(dp[i-1][j-a[i]]+a[i],dp[i-1][j]);
else
dp[i][j]=dp[i-1][j];
}
if(dp[n][size]==0&&zero==0)
printf("Case %d: -1\n",num);
else
printf("Case %d: %d\n",num,dp[n][size]/2);
}
}