suma

Tradiţia este ca, la ieşirea la pensie, pentru fiecare zi de activitate în slujba sultanului, marele vizir să primească o primă stabilită de marele sfat al ţării. Astfel, vizirul Magir a primit pentru doar $5$ zile de activitate prima totală de $411$ galbeni, deoarece sfatul ţării a hotărât pentru ziua întâi o sumă de $53$ de galbeni, pentru ziua a doua $200$ de galbeni, pentru ziua a treia $12$ galbeni, pentru ziua a patra $144$ de galbeni, iar pentru ziua a cincea doar $2$ galbeni.

Vizirul Jibal, celebru pentru contribuţia adusă la rezolvarea conflictului din zonă, primeşte dreptul ca, la ieşirea la pensie, să modifice sumele stabilite de sfatul ţării, dar nu foarte mult. El poate uni cifrele sumelor stabilite şi le poate despărţi apoi, după dorinţă, astfel încât, suma primită pe fiecare zi să nu depăşească $999$ de galbeni şi să primească cel puţin un galben pentru fiecare dintre zilele de activitate. Astfel, dacă are doar $5$ zile de activitate, plătite cu $23$, $417$, $205$, $5$ şi respectiv $40$ de galbeni, în total $680$ de galbeni, el poate opta pentru o nouă distribuţie a cifrelor numerelor stabilite de marele sfat astfel: pentru prima zi cere $2$ galbeni, pentru a doua $3$, pentru a treia $417$, pentru a patra $205$ şi pentru a cincea $540$ de galbeni, primind astfel $1 \ 167$ de galbeni în total.

Cerinţă

Pentru numărul de zile $n$ şi cele $n$ sume stabilite de sfatul ţării pentru Jibal, scrieţi un program care să determine cea mai mare primă totală care se poate obţine prin unirea şi despărţirea cifrelor sumelor date.

Date de intrare

Fişierul de intrare suma.in conţine:

• pe prima linie un număr natural n reprezentând numărul de zile de activitate
• pe linia următoare, n numere naturale separate prin spaţii $s_1$, $s_2$, $\dots$, $s_n$ reprezentând sumele atribuite de sfatul ţării.

Date de ieșire

Fişierul de ieşire suma.out va conţine o singură linie pe care va fi afişat un singur număr natural reprezentând prima totală maximă care se poate obţine.

Restricții și precizări

• $1 < n < 501$
• $0 < s_i < 1 \ 000$
• În orice distribuţie, fiecare sumă trebuie să fie o valoare proprie (să nu înceapă cu $0$).
• Orice sumă dintr-o distribuţie trebuie să fie nenulă.
• Pentru $20\%$ din teste, $n \leq 10$, pentru $50\%$ din teste $n \leq 50$.

Exemplul 1

suma.in

3
58 300 4

suma.out

362

Explicație

Prima maximă ($362$) se obţine chiar pentru distribuţia: $58 \ 300 \ 4$.

Exemplul 2

suma.in

5
23 417 205 5 40

suma.out

1608

Explicație

Prima maximă ($1 \ 608$) se obţine pentru distribuţia: $2 \ 341 \ 720 \ 5 \ 540$.