În zorii zilei, harnicele albinuţe se pregătesc să zboare la cules de nectar. În apropierea stupului, se află o grădină fermecată cu N
flori, numerotate 1
, 2
,… N
. Pentru fiecare floare se cunoaște numărul de petale.
Anumite flori din grădină pot fi flori capcană. O astfel de floare are un număr prim de petale. Dacă o albină s-ar aşeza pe corola florii capcană, atunci floarea i-ar fura o cantitate de nectar egală cu numărul ei de petale.
Alte flori pot fi florile abundenţei. Numărul de petale ale florii abundenţei are un număr impar de divizori. Dacă o albină s-ar aşeza pe corola unei astfel de flori, atunci ea i-ar dărui albinuţei o cantitate de nectar egală cu triplul numărului ei de petale.
Celelalte flori pot fi flori obişnuite. Dacă o albină s-ar aşeza pe corola unei flori obişnuite, atunci floarea i-ar dărui albinuţei o cantitate de nectar egală cu numărul ei de petale.
Regina stupului, le-a poruncit albinuţelor să adune cea mai mare cantitate de nectar care se poate culege din grădină, altfel … vor fi alungate din stup.
Cerinţă
Scrieţi un program care să citească numerele naturale N
și numărul de petale ale fiecărei flori şi care să determine cantitatea maximă C
de nectar pe care albinuţele o pot aduna din grădina fermecată.
Date de intrare
Programul citește de la tastatură numărul n
, iar apoi n
numere naturale, reprezentând numărul de petale ale fiecărei flori.
Date de ieșire
Programul va afișa pe ecran numărul C
.
Restricții și precizări
1 ≤ n ≤ 100 000
- fiecare floare are cel mult
10 000
petale - Nectarul unei flori poate fi cules de o singură albină.
- Cantitatea maximă
C
de nectar culeasă este un număr natural,C ≤ 2 000 000 000
Exemplu:
Intrare
8 25 13 10 7 1 12 31 102
Ieșire
202
Explicație
Cantitatea maximă de nectar se obţine din florile 1
, 3
, 5
, 6
şi 8
. C=3x25+10+3x1+12+102=202