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ò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, \dots, 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

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

Sample Input 1

5
1 2 4 5 2

Sample Output 1

7

Sample Input 2

5
9 8 4 5 13

Sample Output 2

17

Subtasks

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