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
a) suma maximă ce se poate obţine schimbând între ele cifrele numerelor iniţiale;
b) un şir de numere pentru care se obţine suma maximă, respectând restricţiile din enunţ.
Date de intrare
Fişierul de intrare cifre5.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 cifre5.out va conţine 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
• 2 ≤ n ≤ 100 000
• Numerele din şirul iniţial sunt numere naturale ≤ 230-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.
Exemple
cifre5.in
cifre5.out
Explicaţii
8
3120
400
1000
50
1
0
37
60
14280
6410
500
10
20
10
0
7330
0
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 14280.