Bài 4 : Chia kẹo (5.0 điểm)

An và Bình có \(n\) gói kẹo, trong đó gói thứ \(i\) chứa \(a_i\) viên kẹo.

An đề xuất một cách chia kẹo như sau. Trước hết, Bình sắp xếp \(n\) gói kẹo theo một hoán vị bất kỳ. Sau đó, các gói kẹo được xét lần lượt theo thứ tự này và được phân vào hai phần, gọi là phần thứ nhất và phần thứ hai.

Tại mỗi bước, khi xét một gói kẹo:

• Nếu tổng số kẹo hiện có trong phần thứ nhất không lớn hơn tổng số kẹo trong phần thứ hai, thì gói kẹo đang xét được đưa vào phần thứ nhất.
• Ngược lại, gói kẹo được đưa vào phần thứ hai.

Sau khi tất cả các gói kẹo đã được phân xong, Bình nhận phần thứ nhất.

Yêu cầu:
Cho dãy \(a_1, a_2, \ldots, a_n\). Hãy xác định một hoán vị của các gói kẹo sao cho tổng số kẹo mà Bình nhận được là lớn nhất có thể.

Input

• Dòng đầu chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,\dots,a_n\) \((a_i \le 1000)\).

Output

In ra một số là tổng số gói kẹo lớn nhất mà Bình nhận được trong cách sắp xếp tối ưu.

Scoring

• Có \(40\%\) số điểm ứng với \(n \le 8\).
• Có \(30\%\) số điểm ứng với \(n \le 13\).
• \(30\%\) số điểm còn lại ứng với \(n \le 1000,\; a_i = i\).

Sample Input 1

3
2 1 3

Sample Output 1

4