Numbers

Pentru un număr natural nenul $x$, definim operația de rotire cu $k$ cifre ca fiind mutarea la final a primelor $k$ cifre ale lui $x$, în aceeași ordine. Operația de rotire cu $k$ cifre este posibilă numai dacă numărul de cifre ale lui $x$ este strict mai mare decât $k$.
Exemple:

• aplicând operația de rotire cu $3$ cifre numărului $123 \ 456$ obținem $456 \ 123$;
• aplicând operația de rotire cu o cifră numărului $222$ obținem $222$;
• aplicând operația de rotire cu două cifre numărului $1 \ 000$ obținem $10$.

Se dă un șir de $n$ numere naturale nenule. Se pot aplica operații de rotire unor numere din șir astfel încât să nu existe două numere rotite cu același număr de cifre.

Cerință

Să se determine suma maximă care se poate obține însumând numerele din șirul dat, după rotirea convenabilă a unor numere din șir, conform specificațiilor din enunț.

Date de intrare

Fișierul de intrare numbers.in conține pe prima linie numărul $n$, iar pe a doua linie un șir de $n$ numere naturale nenule, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire numbers.out va conține o singură linie pe care va fi scrisă suma maximă obținută.

Restricții și precizări

• $1 \leq n \leq 10 \ 000$
• Numerele din șir sunt numere naturale nenule și au cel mult $15$ cifre.

Exemplul 1

numbers.in

3
2 15 31

numbers.out

84

Explicație

Se rotește $15$ cu o cifră și se obține $51$. $2 + 51 + 31 = 84$.

Exemplul 2

numbers.in

4
17 15 204 1

numbers.out

507 

Explicație

Se rotește $17$ cu o cifră și $204$ cu două cifre. Se obține suma $71 + 15 + 420 + 1 = 507$.

Exemplul 3

numbers.in

4
21 31 42 87

numbers.out

181

Explicație

Nu se rotește niciun număr. Se obține suma maximă $21 + 31 + 42 + 87 = 181$.

Exemplul 4

numbers.in

4
23 113 45719 55588

numbers.out

183469

Explicație

Se rotește $23$ cu o cifră, $113$ cu două cifre, $45 \ 719$ cu $4$ cifre și $55 \ 588$ cu $3$ cifre. Se obține suma maximă $32 + 311 + 94 \ 571 + 88 \ 555 = 183 \ 469$.