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 1167 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 suma2.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 s1, s2, ..., sn reprezentând sumele atribuite de sfatul ţării.
Date de ieşire
Fişierul de ieşire suma2.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
1<n<501
0<si<1000, pentru orice 1 ≤ i ≤ n
Î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 ≤ 10, pentru 50% din teste n ≤ 50.
Exemple
suma2.in
suma2.out
Explicaţii
3
58 300 4
362
Prima maximă (362) se obţine chiar pentru distribuţia: 58 300 4
5
23 417 205 5 40
1608
Prima maximă (1608) se obţine pentru distribuţia: 2 341 720 5 540