Mai mulţi prieteni iubitori ai muntelui au parte de o adevărată aventură, într-una din zilele vacanţei de iarnă. Surprinşi de dificultatea traseului ales spre parcurgere şi de înrăutăţirea rapidă a condiţiilor meteo (ninsoare şi viscol) îşi dau seama, odată cu lăsarea întunericului, că ar fi mai bine să se adăpostească pe timpul nopţii, urmând să revină la cabană în dimineaţa zilei următoare. Norocul pare să le surâdă în cele din urmă. Pe partea cealaltă a prăpastiei la marginea căreia se află, se zăreşte un refugiu. Cercetând împrejurimile, descoperă un podeţ din lemn care i-ar putea ajuta să traverseze prăpastia. După o evaluare mai atentă, realizează că traversarea nu va fi deloc uşoară, pentru că există câteva traverse lipsă, iar starea podeţului permite traversarea sa de către cel mult 2 persoane, la un moment dat. Vizibilitatea este extrem de redusă şi mai există o singură lanternă funcţională ce va trebui folosită judicios pentru traversarea în siguranţă a tuturor membrilor grupului. Traversarea se va face alternativ în ambele sensuri, pentru a putea readuce lanterna celor care n-au traversat încă.
Cerinţă
Cunoscând numărul membrilor grupului, timpul fiecăruia de traversare (exprimat în secunde) şi ştiind că, la o traversare în care sunt angajaţi doi membri, timpul este dat de timpul de traversare al celui mai lent dintre ei, determinaţi timpul total minim necesar pentru ca toţi membrii grupului să traverseze prăpastia.
Date de intrare
Datele de intrare se preiau din fişierul prieteni2.in. Acesta conţine pe prima linie valoarea n, adică numărul prietenilor, iar pe următoarele n linii câte un număr pe linie, numărul ti aflat pe linia i+1 din fişier, reprezentând timpul (exprimat în secunde) în care persoana i din grup poate traversa singură podeţul.
Date de ieşire
Fişierul de ieşire prieteni2.out va conţine o singură linie pe care va fi scris timpul minim total (exprimat în secunde) necesar pentru ca toţi cei n membri ai grupului să traverseze prăpastia.
Restricţii
1<=n<=1000
În orice moment pot traversa podeţul cel mult 2 membri ai grupului 1<= ti <= 1000
Pot exista mai multe persoane cu acelaşi timp de traversare.
Exemple
prieteni2.in
prieteni2.out
Explicaţii
3
2
3
5
10
Mai întâi traversează persoanele 1 şi 2, având timpii 2, respectiv 3 secunde. Timpul de traversare la această trecere este dat de timpul cel mai mare: 3 secunde. Se întoarce apoi persoana 1 cu lanterna, timpul de traversare fiind de 2 secunde. La a treia traversare, trec persoanele 1 şi 3, având timpii 2, respectiv 5 secunde. De data aceasta, timpul de traversare la această trecere este dat de timpul cel mai mare: 5 secunde. Timp total: 3+2+5=10 secunde.
Aceasta este una dintre strategiile posibile. O altă soluţie corectă: traversează mai întâi persoana 1 cu persoana 3, se întoarce persoana 1 şi traversează apoi persoana 1 cu persoana 2, şi în acest caz se obţine acelaşi timp minim de 10 secunde.