Phú ông làng XYZ rất giàu có, ông có ~ n ~ viên kim cương, viên thứ ~ i ~ có giá trị ~ a_i ~. Nhân dịp sinh nhật lần thứ 101 của mình, ông đem ~ n ~ viên kim cương này chia cho hai cô con gái sao cho số viên kim cương của cô em không nhỏ hơn của cô chị.

Phú ông cho phép cô chị được chọn trước phần của mình. Là người am hiểu về kim cương, cô chị biết rõ giá trị của từng viên nên cô chọn sao cho tổng giá trị các viên kim cương mình nhận được là lớn nhất.

Yêu cầu: Hãy cho biết tổng giá trị lớn nhất của các viên kim cương mà cô chị chọn sau khi để lại số lượng viên kim cương không nhỏ hơn của mình cho cô em.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ~ n (2 ≤ n ≤ 10^6) ~ là số viên kim cương.

• Dòng thứ hai chứa ~ n ~ số nguyên dương ~ a_1,a_2,…,a_n ~ ~ (1 ≤a_i≤1000 ~), với ~ a_i ~ là giá trị của viên kim cương thứ ~ i ~.

Các số trên một dòng cách nhau ít nhất một dấu cách.

Kết quả: Một số nguyên duy nhất là tổng giá trị lớn nhất của các viên kim cương mà cô chị đã chọn.

Ví dụ:

Input

6
2 4 1 3 3 5 

Output

12