cifre

Maia tocmai a învăţat la şcoală să facă adunări cu numere naturale având mai multe cifre. Pentru că îi place foarte mult matematica s-a apucat să scrie pe o foaie multe numere naturale, cu una sau mai multe cifre, şi a început să le adune.

După o vreme s-a cam plictisit şi s-a gândit să afle cea mai mare sumă ce s-ar putea obţine dacă s-ar schimba între ele cifrele numerelor de pe foaie. Are însă o singură dorinţă: după ce schimbă cifrele între ele să rămână acelaşi număr de numere cu o cifră, acelaşi număr de numere cu două cifre şi aşa mai departe.

Cerință

Scrieţi un program care să determine:

1. suma maximă ce se poate obţine schimbând între ele cifrele numerelor iniţiale;
2. un şir de numere pentru care se obţine suma maximă, respectând restricţiile din enunţ.

Date de intrare

Fișierul de intrare cifre.in conține pe prima linie un număr natural $n$ reprezentând numărul de numere scrise de Maia pe foaie. Următoarele $n$ linii conţin cele $n$ numere naturale scrise iniţial pe foaie, câte un număr pe fiecare linie.

Date de ieșire

Fișierul de ieșire cifre.out va conține pe prima linie pe prima linie un număr natural $S$ reprezentând suma maximă obţinută. Pe următoarele $n$ linii vor fi scrise $n$ numere naturale, câte un număr pe o linie, reprezentând un şir de numere pentru care se obţine suma maximă, respectând restricţiile din enunţ.

Restricții și precizări

• $2 \leq n \leq 100 \ 000$
• Numerele din şirul iniţial sunt numere nenegative $\leq 2^{30}-1$.
• Numerele din şirul afişat nu vor conţine zerouri nesemnificative.
• Dacă există mai multe şiruri pentru care se obţine suma maximă conform restricţiilor din enunţ, se va afişa oricare dintre acestea.
• Pentru afişarea corectă a sumei maxime se acordă $40\%$ din punctaj, punctajul integral obţinându-se pentru rezolvarea corectă a ambelor cerinţe.

Exemplu

cifre.in

8
3120
400
1000
50
1
0
37
60

cifre.out

14280
6410
500
10
20
10
0
7330
0

Explicație

Se observă că atât în şirul iniţial, cât şi în cel final sunt $2$ numere de $4$ cifre, un număr de $3$ cifre, $3$ numere de două cifre şi două numere de o cifră.

De asemenea, numerele din şirul afişat conţin în total aceleaşi cifre ca numerele din şirul din fişierul de intrare.

Suma maximă care se poate obţine este $14\ 280$.