Đề nâng cao kiến thức của mình, An và Bình quyết định đến thư viện để đọc sách. Một ngày nọ, họ mượn được n cuốn sách từ thư viện và dự định sẽ đọc hết n cuốn sách này. Cuốn sách thứ i sẽ cần t phút đề đọc. Và do hai người bạn mượn quá nhiều sách dẫn đến thư viên không cho phép mượn quá lâu. Vì vậy, thư viện cần tính toán tổng số thời gian tối thiều cần thiết để cả hai bạn cùng đọc hết n cuốn sách này với quy định như sau:

• Tại mỗi thời điểm, mỗi bạn sẽ chỉ được phép đọc một cuốn sách.

• Tại mỗi thời điểm, mỗi cuốn sách chỉ được đọc bởi duy nhất một người.

• Khi đã đọc cuốn sách nào đó thì An và Bình sẽ phải đọc từ đầu đến cuối.

Yêu câu: Hãy giúp thư viện tính tổng thời gian tối thiểu cần thiết đê hai bạn cùng đọc hêt n cuốn sách.

Dữ liệu: Từ tệp văn bản DOCSACH.INP có cấu trúc:

• Dòng đầu tiên của đầu vào là một số nguyên n thể hiện số lượng sách.

• Dòng thứ 2 gồm n số nguyên dương cách nhau bởi một khoảng trắng, số thứ i tương ứng là thời gian ti (số phút) đọc cuốn sách thứ i (0 < t, ≤ 10°).

Kết quả: Ghi vào tệp văn bản DOCSACH.OUT gồm một số nguyên duy nhất thể hiện tổng số thời gian tối thiểu cần thiết để cả hai bạn cùng đọc hết n cuốn sách.

Input:

3
3 8 2

Output:

16

Giải thích: An đọc cuốn sách thứ nhất và thứ ba hết 3+2=5 phút, trong lúc đó Bình sẽ đọc cuốn sách thứ hai hết 8 phút. An sẽ phải chờ thêm 3 phút nữa để lấy cuốn sách thứ hai đọc (sau khi Bình đọc xong) vậy An dùng tổng cộng 5+3+8=16. Trong lúc đó, Bình dùng 5 phút để đọc cuốn sách thứ nhất và thứ ba. Vậy Bình dùng tổng cộng 8+5=13 phút. Do đó, 16 phút là thời gian tối thiểu cần thiết để hai bạn có thể đọc xong ba cuốn sách ở ví dụ.

Ràng buộc:

• Có 50% số điểm của bài có 0 < n ≤ 10^3.

• Có 50% số điểm của bài có 10^3 < n ≤ 2x10^5.