1.
/*
 * FWP, AusgewŠhlte Probleme aus dem ACM Programming Contest, SS10
 * Problem: 10032 tug of war
 *
 * @author Martin Lambeck
 * @version 1.0, 31.10.2010
 *
 * Method : dp
 * Status : Accepted
 * Runtime: 1.544
 *
 */

#include <stdio.h>
#include <memory.h>

#define WEIGHT_RANGE 90001
#define OFFSET 45000

bool first = true;

typedef unsigned long long uint64;

//if a[X] has the bit Y (starting at 0) set,
//then there is a configuration where exactly Y people are in group 1, and the sum of their weights is X.
//multiple bits can be set
uint64 *a = new uint64[WEIGHT_RANGE];
uint64 *b = new uint64[WEIGHT_RANGE];
int weight[101]; //weight of the people

void testcase()
{
	int pers, sum=0;//number of person, sum of weights
	scanf("%d", &pers);

	for (int i = 0; i < pers; i++)
		scanf("%d", weight+i);

	for (int i = 0; i < pers; i++)
			sum += weight[i];

	memset(a, (uint64) 0, WEIGHT_RANGE * sizeof(uint64)); //clear

	a[OFFSET + weight[0]] = 2; //bit 1 (starting at 0)
	a[OFFSET - weight[0]] = 1; //bit 0

	uint64 *prev = b, *cur = a, *tmp;

	for (int i = 1; i < pers; i++)
	{
		tmp = cur; //use only two arrays, but alternate them on each run
		cur = prev; //cur is to be filled (clear before)
		prev = tmp; //prev is the array of the previous person

		int w = weight[i];

		memset(cur, (uint64) 0, WEIGHT_RANGE * sizeof(uint64));

		for (int j = 0; j < WEIGHT_RANGE; j++)
		{
			if (prev[j] > 0)
			{
				cur[j+w] |= prev[j] << 1; //add person i to group 1
				cur[j-w] |= prev[j]; //add person i to group 2
			}
		}
	}

	int diff = -1; //difference of total weight between the two teams
	uint64 p1 = pers/2; //half of the people must be in group 1
	uint64 p2 = (pers+1)/2; //if the number of persons is odd...

	uint64 pattern = ((uint64)1 << p1) | ((uint64)1 << p2); //bitmask

	for (int i = 0; i <= OFFSET && diff < 0; i++)
		if (((cur[OFFSET+i] | cur[OFFSET-i]) & pattern) > 0)
			diff = i; //optimal solution

	printf("%s%d %d\n", first ? "" : "\n", (sum-diff)/2, (sum+diff)/2);

	first = false;
}

int main()
{
	int cases;
	scanf("%d", &cases);

	for (int i = 0; i < cases; i++)
		testcase();

	delete a;
	delete b;

	return 0;
}