Ở giữa đêm, một nhóm du khách muốn qua một cây cầu cũ và đổ nát. Họ đã chỉ có một chiếc đèn pin, ánh sáng của đèn pin chỉ cho phép nhiều nhất hai khách du lịch qua cầu cùng lúc. Các du khách không thể qua cầu mà không có đèn pin hoặc trong các nhóm lớn hơn hai trừ khi họ muốn rơi xuống sông. Môi du khách cần một lượng thời gian nhất định để vượt qua cây cầu. Hai khách du lịch qua cầu với nhau cần một khoảng thời gian của người chậm nhất trong nhóm hai người qua cầu. Hãy tính thời gian ngắn nhất để nhóm du khách qua cầu?

Ví dụ: Giả sử nhóm du khách có ~4~ người. Người đầu tiên của họ cần 6 phút để vượt qua cây cầu, người thứ hai là 7 phút, người thứ ba là 10 phút và người thứ 4 là 15 phút. các hình ảnh sau đây cho thấy làm thế nào họ có thể vượt qua cây cầu trong 44 phút. Tuy nhiên, họ có thể làm nó nhanh hơn. Làm thế nào ?

Các con số trong vòng tròn biểu thị thời gian (theo phút) qua cầu của khách du lịch

Yêu cầu

Tìm thời gian ngắn nhất để du khách qua cây cầu

Input

• Dòng đầu tiên chứa số nguyên dương n là số khách du lịch ~(1 \le n \le 10^5)~
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng ghi một số nguyên dương là thời gian để du khách thứ ~i~ qua cầu. Tổng thời gian qua cầu của ~n~ du khách du lịch không vượt quá ~10^9~.

Output

• Gồm một số duy nhất là thời gian ngắn nhất để đoàn du khách qua cầu

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

4
6
7
10
15

Output

42