Có ~n~ cuốn sách, Kotivalo và Justiina sẽ đọc hết tất cả chúng. Với mỗi cuốn sách, bạn biết thời gian cần để đọc nó.

Cả hai cùng đọc từng cuốn sách từ đầu đến cuối, và họ không thể đọc cùng một cuốn sách tại cùng một thời điểm. Hãy tính tổng thời gian tối thiểu cần thiết?

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~n~: số lượng cuốn sách.

Dòng thứ hai chứa ~n~ số nguyên ~t\_1,t\_2,\dots,t\_n~: thời gian cần để đọc mỗi cuốn sách.

Kết quả

In ra một số nguyên: tổng thời gian tối thiểu.

Giới hạn

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le t\_i \le 10^9~

Ví dụ

Dữ liệu vào:

3
2 8 3

Kết quả:

16