Cerința

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.

Valori litere: A,a = 1; B,b = 2; C,c = 4; D,d = 8; E,e = 16; F,f = 32; … ; Z,z = 33.554.432

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) + Valoare(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, DAC , mai jos este ilustrată una dintre posibilitățile de unire:

Șir inițial cuvinte: Abac, cade, DAC. Se unesc mai întâi cuvintele Abac și cade și se obține ABCDE, cu costul 26, iar șirul devine ABCDE, DAC. Cost parțial: 26

Șir actualizat de cuvinte: ABCDE, DAC. Se unesc ABCDE și DAC și se obține ABCDE, cu costul 18 , calculat prin însumarea valorilor literelor B și E. Cost parțial: 18

Cuvânt final: ABCDE. Cost total: 26 + 18 = 44.

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.

Observație: Nu se pot uni cuvintele Abac și DAC din șirul inițial, pentru că nu sunt alăturate, șirul de cuvinte fiind liniar.

Cerința este, ca, pentru un șir de N cuvinte, să se afle cuvântul final rezultat în urma unirii a două câte două cuvinte alăturate și costul total minim necesar obținerii acestuia.

Date de intrare

Fișierul de intrare scrabble.in conține pe prima linie 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 de ieșire 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 ≤ N ≤ 100, cuvintele nu au mai mult de 100 de litere
• Pentru teste în valoare de 20 de puncte, N <= 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.