Scrabble

Fiind în vacanță, RAU-Gigel petrece mult timp jucându-se pe telefon. El are un joc cu cuvinte, de tip Scrabble, în care piesele sunt inscripționate cu litere (mici sau mari, ale alfabetului englez), fiecare literă din alfabet având o valoare cunoscută, număr natural. Valoarea unui cuvânt este egală cu suma valorilor literelor din cuvânt, fără a se ține cont de frecvența lor.

De exemplu, valoarea cuvântului Abac este $Val($Abac$) = Val($A$) + Val($b$) + Val($c$) = 1+2+4=7$. Prin unirea a două cuvinte se obține cel mai mic (alfanumeric) cuvânt format din toate literele prezente în cele două cuvinte, fără să ținem cont de tipul literei (mică/mare) sau de numărul de apariții. Notăm acest cuvânt cu $a*b$. Costul unirii dintre două cuvinte este obținut prin însumarea valorilor literelor prezente în $a*b$, dar care nu sunt în $a$, respectiv, care nu sunt în $b$, ignorând tipul lor.

De exemplu, prin unirea cuvintelor $a =\$Abac și $b =\$cade se obține cuvântul $a*b =\$ABCDE, iar costul unirii poate fi calculat astfel: $Val($DE$) + Val($B$) = 24 + 2 = 26$.

Aplicația lui RAU-Gigel generează un șir liniar cu $N$ cuvinte, iar RAU-Gigel trebuie să unească două câte două cuvinte alăturate din șir, oricare, plătește costul necesar unirii lor, apoi înlocuiește în șir cele două cuvinte cu cuvântul obținut prin unire. La final, din șirul dat va rămâne un singur cuvânt, iar, pentru obținerea lui, RAU-Gigel va plăti suma tuturor costurilor generate pe parcurs.

Dacă, de exemplu, avem $3$ cuvinte: Abac, cade și DAC, mai jos este ilustrată una dintre posibilitățile de unire:

Cel mai mic cuvânt alcătuit prin unirea celor $3$ cuvinte, fără a ține cont de tipul literei (mică/mare) sau frecvență, va fi ABCDE, iar costul total necesar obținerii lui, conform alegerilor de mai sus, va fi $26 + 18 = 44$. Dar mai este o variantă: RAU-Gigel poate uni mai întâi cuvintele cade și DAC și obține ACDE, cu costul $16$, apoi unește Abac și ACDE și obține ABCDE, cu costul $26$. Costul total va fi de această dată: $16 + 26 = 42$.

Așadar, costul total minim este dat de cea de-a doua variantă și este $42$.

Cerință

Dându-se un sir de $N$ cuvinte, să se afle cuvântul final rezultat în urma reuniunii a două câte două cuvinte alăturate și costul total minim necesar obținerii acestuia.

Date de intrare

Fișierul scrabble.in conține pe primul rând numărul natural nenul $N$, reprezentând numărul de cuvinte. Pe următoarele $N$ rânduri se află cele $N$ cuvinte.

Date de ieșire

Fișierul scrabble.out va conține, pe un sigur rând, cele două valori: cuvântul final și costul total minim necesar obținerii lui, conform cerinței. Cele două valori sunt separate printr-un spațiu.

Restricții și precizări

• $2 \leq N \leq 10^2$, cuvintele nu au mai mult de $100$ de litere.
• Pentru teste în valoare de 20 de puncte, $N \leq 4$.
• Pentru teste în valoare de încă 10 de puncte, toate cele $N$ cuvinte au aceeași valoare.
• Pentru teste în valoare de încă 20 de puncte, orice cuvânt include, în componența sa, literele cuvintelor din stânga lui (ignorând tipul literei), plus, eventual, alte litere.
• Tipul literei = literă mică sau mare.

Exemplu

scrabble.in

3
Abac
cade
DAC

scrabble.out

ABCDE 42

Explicație

Cel mai mic cuvânt alcătuit prin unirea celor $3$ cuvinte, fără a ține cont de tipul literei (mică/mare) sau frecvență, este: ABCDE, iar costul total minim necesar obținerii lui este $42$.