구명정 무게 맞추기

설계 결함이 많은 대형 유람선이 첫 항해 도중 침몰하기 시작했다. 배에는 구명정이 두 척 있고, 각 구명정에는 승객의 절반이 탈 수 있다. 한쪽에 무게가 쏠리면 그 구명정이 가라앉을 위험이 있으므로 두 구명정에 실리는 몸무게 합을 최대한 비슷하게 맞춰야 한다.

승객 $N$명은 모두 구명정에 타야 하고, 두 구명정에 타는 인원은 같아야 한다. $N$이 홀수여서 정확히 반으로 나눌 수 없으면 한 척에 $\lfloor N/2 \rfloor$명, 다른 한 척에 $\lceil N/2 \rceil$명이 탄다. 이 조건을 지키면서 두 몸무게 합의 차이를 최소로 만들었을 때, 두 구명정의 몸무게 합을 구하라.

첫 줄에 테스트 케이스의 수 $C$가 주어진다.

각 테스트 케이스의 첫 줄에는 구명정에 타야 하는 사람의 수 $N$이 주어진다 ($1 \le N \le 5000$). 다음 $N$개의 줄에는 승객 한 명의 몸무게 $W$가 한 줄에 하나씩 주어진다 ($1 \le W \le 1000$).

각 테스트 케이스마다 몸무게 합의 차이가 최소가 되도록 나누었을 때 두 구명정의 몸무게 합을 한 줄에 출력한다. 두 값이 다르면 작은 값을 먼저 출력하고, 두 값은 공백 하나로 구분한다.