Bài toán: Đọc sách tối ưu

Đề bài

Có ~ n ~ quyển sách, và Kotivalo và Justiina muốn đọc tất cả chúng. Mỗi quyển sách mất ~ t_i ~ thời gian để đọc.

Quy tắc:

• Cả hai người đều đọc từ đầu đến cuối, và không thể đọc cùng một quyển sách cùng lúc.

Yêu cầu: Tìm tổng thời gian tối thiểu để cả hai người đọc xong tất cả các quyển sách.

Input

• Dòng đầu tiên chứa số nguyên ~ n ~ (~ 1 \leq n \leq 2 \times 10^5 ~): số lượng sách.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ t_1, t_2, \ldots, t_n ~ (~ 1 \leq t_i \leq 10^9 ~): thời gian cần để đọc từng quyển sách.

Output

• Một số nguyên: tổng thời gian tối thiểu cần để hoàn thành việc đọc tất cả sách.

Ràng buộc

• ~ 1 \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq t_i \leq 10^9 ~

Ví dụ

Input:

3
2 8 3

Output:

16

Giải thích:

• Kotivalo đọc sách 1 và 3 (~ 2 + 3 = 5 ~).
• Justiina đọc sách 2 (~ 8 ~).
• Tổng thời gian = ~ \max(5, 8)*2 = 16 ~.