Sắp lịch

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.

Mỗi buổi dạy diễn ra liên tục từ lúc bắt đầu đến lúc kết thúc. Hai giáo sư cùng bắt đầu ở thời điểm $0$; mỗi giáo sư có thể nghỉ giữa các buổi dạy và dạy các lớp theo thứ tự tùy ý.

Yêu cầu: Hãy tính tổng thời gian ít nhất (tính từ thời điểm $0$ đến khi cả hai giáo sư đều dạy xong) để cả hai giáo sư tập huấn cho cả $n$ lớp học theo mô tả ở trên.

Dữ liệu vào

• Dòng đầu ghi số $n$ ($1\le n\le 300000$).
• 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 300000$).

Dữ liệu ra

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.

Ràng buộc

• $1\le n\le 300000$.
• $0<a_i\le 300000$.

Ví dụ