C++ :

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>

using namespace std;

int n;
int a[1010];
bool f[10100];

int solve(){
	memset(f,false,sizeof(f));
	f[0] = true;
	int sum = 0;
	for(int i = 1;i <= n;++i)
		sum += a[i];
	for(int i = 1;i <= n;++i)
		for(int j = a[i];j <= sum;++j)
			f[j] |= f[j - a[i]];
	int ans = 0x3f3f3f3f;
	for(int i = 0;i <= sum;++i){
		if(!f[i])
			continue;
		int t = max(sum - i,i);
		ans = min(ans,t);
	}
	return ans;
}

int main(){
	int T;
	scanf("%d",&T);
	for(int caseT = 1;caseT <= T;++caseT){
		scanf("%d",&n);
		for(int i = 1;i <= n;++i)
			scanf("%d",&a[i]);
		solve();
		printf("Case %d: %d\n",caseT,solve());
	}
	return 0;
}