10032.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>

#include <cassert>

using namespace std;

#define NN 128
#define MM (NN*512)

int T, n;
int a[NN];
long long dp[MM];
int ans, A, B, sum;

int main(void) {
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		sum = 0;
		for(int i = 1; i <= n; i++) scanf("%d", &a[i]), sum += a[i];
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		for(int i = 1; i <= n; i++)
			for(int j = MM-1; j >= 0; j--)
				if(j >= a[i] && dp[j-a[i]])
					dp[j] |= (dp[j-a[i]] << 1);

		ans = 0x3f3f3f3f;
		for(int j = 0; j < MM; j++) {
			if(dp[j]&(1<<(n/2)) && ans > abs(sum - 2*j)) {
				ans = abs(sum - 2*j);
				A = sum - j;
				B = j;
			}
		}
		if(A > B) swap(A, B);
		printf("%d %d\n", A, B);
	}

	return 0;
}