Hai giáo sư X và Y cùng tham gia đợt tập huấn cho ~n~ lớp học (ta đánh số các lớp học từ 1 đến ~n~). Thời gian cho một buổi học ở lớp thứ ~i~ là ~a_i~. Biết rằng:

• Tại một thời điểm, mỗi giáo sư chỉ tập huấn cho một lớp và hai giáo sư làm việc độc lập (không có lớp học nào phải nghe cả hai Giáo sư dạy tại cùng thời điểm).
• Thời gian dạy cho lớp thứ ~i~ luôn là ~a_i~ phút (dù người dạy là giáo sư X hay Giáo sư Y).
• Mỗi giáo sư phải dạy đủ ~n~ lớp học, không được bỏ qua lớp nào.

Yêu cầu: Hãy tính tổng thời gian ít nhất để cả hai giáo sư tập huấn cho cả ~n~ lớp học theo mô tả ở trên.

Input

• Dòng đầu ghi số ~n~ (~1 \le n \le 300.000~)
• Dòng tiếp theo ghi ~n~ số ~a_1, a_2, \dots, a_n~ với ~a_i~ là thời gian học của lớp thứ ~i~ (~0 < a_i \le 300.000~).

Output

Ghi ra một số duy nhất là tổng thời gian ít nhất để cả hai giáo sư hoàn thành bài giảng của mình cho cả ~n~ lớp.

Sample Input 1

3
2 2 2

Sample Output 1

6