Chia tiền thưởng

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

Mỗi tờ tiền thuộc về đúng một trong ba phần: của An, của Bình, hoặc đem đi đầu tư (không được cắt nhỏ tờ tiền). Nếu không có cách nào để mỗi người nhận một số tiền dương bằng nhau thì cả hai đều nhận $0$ và toàn bộ số tiền được đ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

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

Dữ liệu ra

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

• $1\le N\le 500$.
• $a_i\ge 1$ và $a_1+a_2+\dots +a_N\le {10}^5$.
• Có $40\%$ số test ứng với $40\%$ số điểm thỏa mãn $N\le 3$.
• $30\%$ số test tiếp theo ứng với $30\%$ số điểm thỏa mãn $N\le 12$.
• $30\%$ số test còn lại ứng với $30\%$ số điểm không có ràng buộc gì thêm.

Ví dụ