Hùng và Dũng là hai anh em, Hùng là anh và Dũng là em. Nhân ngày Quốc tế Thiếu nhi, mẹ mua n gói kẹo cho hai anh em. Vấn đề hóc búa là chia các gói kẹo này. Để kiểm tra độ thông minh của hai con, mẹ đưa ra yêu cầu chia theo qui tắc: Hai anh em chọn một số gói kẹo sao cho có thể chia thành hai phần với số lượng kẹo trong mỗi phần bằng nhau và tổng số kẹo trong các gói không được chia là nhỏ nhất có thể. Số kẹo trong các gói không được chia mẹ sẽ dành cho Dũng (em - bé hơn!!!).

Hỏi rằng tổng số kẹo mà Dũng nhận được là bao nhiêu?

Input

• Dòng đầu tiên ghi số nguyên dương \(n\) (\(n\le 500\)) số gói kẹo mà mẹ mua
• \(n\) dòng tiếp theo, dòng thứ \(i\) ghi \(c_i\) là số kẹo có trong gói thứ \(i\). Tổng số kẹo trong \(n\) gói kẹo không vượt quá 100000.

Output

• Số kẹo mà Dũng nhận được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n\le 13\)
• Subtask \(2\) (\(70\%\) số điểm): \(n\le 50\), tổng số kẹo \(\le 1000\)

Example

5
2
3
5
8
13  

18