Nguồn: Học sinh Giỏi THPT Hà Nội năm 2022 - 2023

Nhờ hoàn thành tốt công việc, An và Bình được công ty thưởng \(N\) tờ tiền. Tờ tiền thứ \(i\) có mệnh giá \(a_i\). Hai bạn muốn chia đôi số tiền thành hai phần bằng nhau bằng cách chia cho mỗi người một số tờ tiền. Vì thế hai bạn quyết định sẽ chọn ra những tờ tiền để tổng số tiền hai bạn nhận được bằng nhau và lớn nhất, phần còn lại (nếu có) sẽ đem đi đầu tư.

Yêu cầu: Hãy giúp hai bạn tính tổng số tiền lớn nhất mà mỗi người nhận được trước khi đầu tư.

Input

Dữ liệu vào từ tệp văn bản CT.INP:

• Dòng đầu tiên chứa số nguyên dương \(N \ (N \le 500);\)
• Dòng thứ hai bao gồm \(N\) số nguyên dương \(a_1, a_2, ..., a_N\) là mệnh giá của những tờ tiền. Tổng giá trị những tờ tiền sẽ không vượt quá \(10^5\).

Output

Kết quả ra tệp văn bản CT.OUT:

• Gồm một dòng duy nhất là số tiền lớn nhất mà mỗi người nhận được.

Example

5
1 2 4 5 2

7

Note

• An có thể chọn những tờ tiền có mệnh giá \(1, 2, 4\).
• Bình chọn những tờ tiền còn lại có mệnh giá \(5, 2\).
• Mỗi người sẽ nhận được tổng số tiền là \(7\). Vì số tiền mỗi người nhận đã bằng nhau và đã chia hết số tiền nên họ sẽ không đầu tư.

5
9 8 4 5 13

17

Note

• An sẽ chọn những tờ tiền có mệnh giá \(9, 8\).
• Bình sẽ chọn những tờ tiền có mệnh giá \(4, 13\).
• Mỗi người sẽ nhận được tổng số tiền là \(17\). Tờ tiền còn lại có mệnh giá \(5\) sẽ đem đi đầu tư.

Constraint

• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài thoả mãn \(N \le 3;\)
• \(30\%\) số test tiếp theo ứng với \(30\%\) số điểm của bài thoả mãn \(N \le 12;\)
• \(30\%\) số test còn lại ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.