사탕 나누기

Sean과 Patrick은 부모님에게서 멋진 사탕 한 봉지를 막 받은 형제이다. 각 사탕 조각에는 양의 정숫값이 있으며, 아이들은 사탕을 둘이 나누려고 한다. 먼저 Sean이 사탕을 두 더미로 나누고 그중 한 더미를 골라 Patrick에게 준다. 그러면 Patrick은 각 더미의 가치를 계산하려고 한다. 한 더미의 가치는 그 더미에 있는 모든 사탕 조각의 가치의 합이다. Patrick이 두 더미의 가치가 같지 않다고 판단하면 울기 시작한다.

안타깝게도 Patrick은 매우 어려서 덧셈을 제대로 할 줄 모른다. 그는 이진수 덧셈을 거의 할 줄 알지만, 두 개의 1을 더할 때마다 항상 올림을 다음 비트로 넘기는 것을 잊는다. 예를 들어 12와(과) (이진수로 1100) 5를(을) (이진수로 101) 더하려 하면, 오른쪽 끝의 두 비트는 올바르게 더하지만 세 번째 비트에서는 올림을 다음 비트로 넘기는 것을 잊는다.

1100
+ 0101
------
  1001

따라서 세 번째 비트에서 발생한 올림 없이 마지막 비트를 더한 뒤의 최종 결과는 9이다(이진수로 1001). 다음은 Patrick의 계산 실력을 보여 주는 몇 가지 다른 예이다.

5 + 4 = 1
7 + 9 = 14
50 + 10 = 56

Sean은 덧셈을 매우 잘하며, 남동생을 울리지 않으면서 가능한 한 큰 가치를 차지하고 싶어 한다. 가능하다면 그는 Patrick이 두 더미의 가치가 같다고 생각하도록 사탕 봉지를 비어 있지 않은 두 더미로 나눈다. 봉지에 든 모든 사탕 조각의 가치가 주어질 때, 이것이 가능한지 알고자 한다. 또한 가능하다면 Sean의 사탕 더미가 가질 수 있는 최대 가치를 구하고자 한다.

제한

1 ≤ T ≤ 100. 1 ≤ $C_{i}$ ≤ $10^{6}$. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ N ≤ 15. 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ N ≤ 1000. 시간 제한: 60초.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 설명된다. 첫 번째 줄에는 봉지에 든 사탕의 수를 나타내는 정수 N 하나가 주어진다. 다음 줄에는 봉지에 든 각 사탕 조각의 가치를 나타내는 N개의 정수 $C_{i}$가 한 칸의 공백으로 구분되어 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작한다. Sean이 Patrick을 울지 않게 하는 것이 불가능하면 y는 단어 "NO"이어야 한다. 그렇지 않으면 y는 Sean이 가질 사탕 더미의 가치여야 한다.