Most - Most

Cestou v autobuse Jožko nemal čo robiť a tak si čas krátil riešením rôznych logických úloh. I našiel takúto úlohu:
"Nad riekou je starý a rozbitý most. Na jednej strane mosta sú štyria ranení muži. Keďže je tma a most je rozbitý, po moste možu prejsť najviac dvaja súčasne a potrebujú k tomu baterku. Baterku ale majú len jednu. Navyše rieka je dosť široká na to, aby baterku mohli prehodiť. Miera zranenia sa líši a tak prechod mosta trvá každému mužovi iný čas: 5 min, 10 min, 20 min a 25 min. Ak idú cez mosta dvaja spoločne, idú rýchlosťou toho pomalšieho. Je celkom jednoduché nájsť postup, aby sa všetci dostali na druhú stranu za 65 minút. Úlohou je nájsť lepšie riešenie - ide to totiž aj za 60 minút."
Jožko riešenie rýchlo našiel. Problém ho však natoľko zaujal, že začal hútať, ako sa zmení riešenie, ak počet mužov alebo ich časy na prechod mosta budú iné.

Úloha

Vytvorte program, ktorý pre zadaný počet mužov a zadané časy potrebné na prechod mosta vypočíta minimálny čas potrebný na prejdenie mosta.

Vstup

Prvý riadok vstupu obsahuje jedno prirodzené číslo N (1 ≤ N ≤ 10) vyjadrujúce počet zranených mužov. Druhý riadok obsahuje N medzerami oddelených čísel - každé z čísel vyjadruje čas potrebný na prechod mosta jedného z mužov. Každý čas trvania prechodu je nenulové prirodzené číslo mešie ako 100.

Výstup

Minimálny čas potrebný na to, aby všetci muži prešli cez most.

Príklad

Vstup:

4
5 10 20 25

Výstup:

60