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

Cả hai sẽ đọc toàn bộ mỗi quyển sách từ đầu đến cuối, nhưng không thể đọc cùng một quyển cùng lúc. Nhiệm vụ của bạn là xác định tổng thời gian tối thiểu cần thiết để cả hai đọc hết tất cả các quyển sách.

Input:

Dòng đầu tiên chứa một số nguyên n — số lượng quyển sách.

Dòng thứ hai chứa n số nguyên t₁, t₂, …, tₙ — thời gian đọc từng quyển sách.

Output:

In ra một số nguyên: tổng thời gian tối thiểu cần thiết để đọc hết tất cả các quyển sách.

Ràng buộc:

~1 \le n \le 2 \cdot 10^5~

~1 \le t_i \le 10^9~

Ví dụ :

Input:

3
2 8 3

Output:

16