Sean và Patrick là hai anh em vừa được bố mẹ cho một túi kẹo ngon. Mỗi viên kẹo có một giá trị nguyên dương. Hai anh em muốn chia số kẹo này cho nhau. Trước tiên, Sean sẽ chia kẹo thành hai đống và chọn một đống để đưa cho Patrick. Sau đó Patrick sẽ cố tính giá trị của mỗi đống, trong đó giá trị của một đống là tổng giá trị của tất cả các viên kẹo trong đống ấy. Nếu Patrick cho rằng hai đống không có giá trị bằng nhau, cậu bé sẽ khóc.

Đáng tiếc, Patrick còn rất nhỏ và chưa biết cộng đúng cách. Cậu gần như biết cộng các số nhị phân, nhưng khi cộng hai bit 1, cậu luôn quên nhớ sang bit tiếp theo. Chẳng hạn, khi muốn cộng 12 (1100 trong hệ nhị phân) và 5 (101 trong hệ nhị phân), cậu cộng đúng hai bit ngoài cùng bên phải, nhưng ở bit thứ ba lại quên nhớ sang bit kế tiếp:

  1100

+ 0101
------
  1001

Vì vậy, sau khi cộng bit cuối cùng mà không có phần nhớ từ bit thứ ba, kết quả cuối cùng là 9 (1001 trong hệ nhị phân). Sau đây là một số ví dụ khác về khả năng tính toán của Patrick:

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

Sean cộng rất giỏi và muốn lấy tổng giá trị lớn nhất có thể mà không làm em trai khóc. Nếu có thể, cậu sẽ chia túi kẹo thành hai đống không rỗng sao cho Patrick nghĩ rằng chúng có cùng giá trị. Với giá trị của tất cả các viên kẹo trong túi, hãy xác định việc chia như vậy có thể thực hiện được hay không; nếu có, hãy tìm giá trị lớn nhất có thể của đống kẹo thuộc về Sean.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test được mô tả bằng hai dòng. Dòng đầu chứa một số nguyên \(N\), là số viên kẹo trong túi. Dòng tiếp theo chứa \(N\) số nguyên \(C_i\), cách nhau bởi một dấu cách, là giá trị của từng viên kẹo.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1). Nếu Sean không thể ngăn Patrick khóc, y phải là từ NO. Ngược lại, y là giá trị của đống kẹo mà Sean sẽ giữ.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le C_i \le 10^6\).

Phân nhóm

• Test Set 1 (Nhìn thấy): \(2 \le N \le 15\).
• Test Set 2 (Ẩn): \(2 \le N \le 1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
5
1 2 3 4 5
3
3 5 6

Case #1: NO
Case #2: 11

Nguồn

Google Code Jam 2011, Vòng loại, bài Candy Splitting.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.