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ư.

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~.

Kết quả ghi 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.

Ràng buộc

• 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.

Ví dụ

Input

5
1 2 4 5 2

Output

7

Giải thích:

• 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ư.

Input

5
9 8 4 5 13

Output

17

Giải thích:

• 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ư.