Програмчлалын олимпиадын бодлогын архив

Coca cola компани Fuji infox компанийн менежерт дараах саналыг тавив. Coca cola компани зар сурталчилгааны өдөрлөгтөө дараах асуудлыг хүмүүст тавих гэсэн боловч тооцоолж чадахгүй байгаа болохоор Fuji infox компанийн программистуудаас нь тусламж авахаар болов.
Энэхүү асуудал нь төрөл бүрийн хэмжээтэй лонхонд ундаанууд хийж тавиад яг дараалсан гурван лонхонд байгаа ундаануудыг ууж болохгүй нөхцөлд тэдгээрээс хамгийн ихдээ хичнээн хэмжээний ундаа уух боломжтойг тогтоох хэрэгтэй болно.Гэхдээ ууж дууссаад хоосон лонхыг байранд нь буцааж тавина. Уухдаа нэг лонхондохоо ууж байж дараагийн лонхыг сонгох ёстой.
Энэ асуудлыг хэрхэн шийдвэрлэх вэ? Та туслана уу!

Input

Эхний мөрөнд лонхны тоо N (N>=4) , дараагийн N мөрүүдэд лонхнуудын хэмжээг илэрхийлсэн Vi натурал тоонууд байрлана.

Output

Ууж болох хамгийн их ундааны хэмжээнээс тогтоно.
Бусад хязгаарлалт: N<=1000, Vi<10000.

Example

Input:
6
6
10
13
9
8
1


Output:
33

Тайлбар: Эхлээд 1,2,4,5-ийг сонгоход.