Maria este mare amatoare de cumpărături. Ea și-a cumpărat în decursul mai multor zile de la magazinul său preferat N
articole de îmbrăcăminte și încălțăminte cu preturile s
1
, s
2
, …, s
N
lei. Iulia, prietena Mariei, observând cumpărăturile, i-a spus:
- Puteai economisi mulți bani. Nu ai văzut promoțiile magazinului? Dacă ai fi cumpărat două produse deodată, cel mai ieftin din cele două l-ai fi cumpărat la jumătate de preț. Iar dacă ai fi cumpărat trei produse deodată, ai fi primit pe cel mai ieftin din cele trei gratuit!
Maria și Iulia s-au decis să afle care ar fi fost suma minimă cheltuită pentru a achiziționa în aceeași ordine cele N
produse, dar grupând câte un produs, câte două sau câte trei.
Cerința
Pentru că cele două fete nu se descurcă așa de bine la informatică, ele te roagă să le ajuți să determine care este această sumă minimă.
Date de intrare
Programul citește de la tastatură un număr natural N
, iar apoi N
numere naturale s
1
, s
2
, …, s
N
separate prin câte un spațiu reprezentând sumele cheltuite pentru fiecare din cele N
produse.
Date de ieșire
Programul va afișa pe ecran un singur număr real, care reprezintă suma minimă ce putea fi cheltuită grupând produsele câte unul, câte două sau câte trei. Numărul real se va afișa cu o zecimală.
Restricții și precizări
4 ≤ N ≤ 1000
- Sumele
s
1
,s
2
, …,s
N
sunt numere naturale cuprinse între1
și1000
Exemplul 1:
Intrare
4 20 100 50 200
Ieșire
320.0
Explicație
Maria trebuia să cumpere primul produs, cheltuind 20
lei, apoi să cumpere ultimele trei produse împreună cheltuind numai 300
de lei, deoarece produsul de 50
lei îl primea gratuit.
Exemplul 2:
Intrare
5 100 27 15 25 400
Ieșire
538.5
Explicație
Maria trebuia să cumpere primele două produse împreună, cheltuind 113.5
lei, apoi să cumpere ultimele trei produse împreună, cheltuind 425
lei. Suma totală cheltuită ar fi fost 113.5 + 425 = 538.5
lei.