În stepa nesfârşită, n canguri s-au aliniat unul lângă celălalt la linia de start, pentru a participa la o cursă în linie dreaptă. La semnalul de începere a cursei fiecare cangur va sări, în ritm constant şi în salturi de aceeaşi lungime, până când toţi cangurii, la ultimul salt, vor ateriza simultan pe linia de finish. Care este lungimea minimă a traseului ştiind că toţi cangurii pleacă în acelaşi moment în cursă şi fiecare face cel puţin 3 salturi pe traseul dat.
Cerinţă
Ştiind numărul cangurilor şi lungimea saltului fiecărui cangur, să se determine lungimea minimă a traseului pe care se poate desfăşura cursa.
Date de intrare
Fişierul de intrare canguri.in conţine pe prima linie n, numărul de canguri iar pe următoarea linie, n numere naturale nenule separate prin câte un spaţiu a1, a2, … an, reprezentând lungimea în metri a saltului fiecărui cangur.
Date de ieşire
Fişierul de ieşire canguri.out va conţine pe prima linie un număr întreg, reprezentând lungimea minimă a traseului cursei, măsurată în metri.
Restricţii
• Lungimea labei picioarelor cangurilor este neglijabilă în raport cu lungimea saltului.
• Lungimea traseului nu depăşeşte 2100000000 metri.
• 1≤n≤500
• 1≤ai≤100, pentru 1≤i≤n
Exemple
canguri.in
canguri.out
Explicaţii
4
12 6 24 8
72
Primul cangur face 6 salturi, al doilea 12 salturi, al treilea 3 salturi iar al patrulea 9 salturi.