Để nâng cao kiến thức của mình, Tùng và Châu 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_i~ 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ì Tùng và Châu 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 ~t_i~ (số phút) đọc cuốn sách thứ ~i~ (~0 < t_i ≤ 10^9~).

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.

Ví dụ đầu vào:

3
3 8 2

Đầu ra:

16

Giải thích:

Tùng đọc cuốn sách thứ nhất và thứ ba hết 3+2 = 5 phút, trong lúc đó Châu sẽ đọc cuốn sách thứ hai hết 8 phút. Tùng sẽ phải chờ thêm 3 phút nữa để lấy cuốn sách thứ hai đọc (sau khi Châu đọc xong) vậy Tùng dùng tổng cộng 5+3+8 = 16. Trong lúc đó, Châu dùng 5 phút để đọc cuốn sách thứ nhất và thứ ba. Vậy Châu 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 ≤ 2×10^5~.