telegraf

Cerință

Până nu demult, comunicaţia la distanţă se făcea cu ajutorul telegrafului. Folosind telegraful, se pot transmite două tipuri de semnale: punct şi linie. În general, dorim să transmitem texte formate din litere ale alfabetului latin şi cifre (în total, $36$ de simboluri). Trebuie deci să folosim o codificare, adică să asociem fiecăruia din cele $36$ de simboluri o succesiune distinctă de linii şi puncte. Pentru a putea decodifica o succesiune recepţionată de linii şi puncte, este necesar ca nici un simbol să nu aibă o codificare identică cu începutul codificării pentru un alt simbol. Să considerăm câteva exemple (presupunând că nu vrem să transmitem decât literele $A, B, C$):

Exemplul $1$ reprezintă o codificare corectă. Exemplul $2$ reprezintă o codificare greşită, pentru că începutul codificării pentru $A$ este identic cu codificarea pentru $B$ (deci, o secvenţă de genul .-- este ambiguă, putând însemna şi $A$ şi $BC$). Exemplul $3$ este de asemenea o codificare greşită pentru că începutul codificării pentru $A$ este identic cu codificarea pentru $C$ (o secvenţă precum .-..-. este ambiguă, putând însemna fie $AB$, fie $CC$).

Se ştie că într-o transmisie telegrafică, punctul durează o secundă, iar linia $2$ secunde. Putem calcula astfel timpul necesar transmiterii unui text.
Folosind codificarea din exemplul $1$, transmiterea textului CABCA = - .. .- - .. durează $11$ secunde. Observaţi că lungimea transmisiei se poate calcula şi astfel: $2(A) + 1(B) + 2(C) = 2(..) + 1(.-) + 2(-) = 2 \cdot 2 + 1 \cdot 3 + 2 \cdot 2 = 11$.

Se consideră un text, dat prin frecvenţa apariţiei fiecărui simbol (dintre cele 36 considerate). Să se găsească durata minimă necesară transmiterii acelui text, folosind o codificare aleasă corespunzător.

Date de intrare

Fişierul telegraf.in conţine o singură linie cu $36$ de numere întregi nenegative, separate prin câte un spaţiu, reprezentând numărul de apariţii ale fiecărui simbol în textul ce trebuie transmis.

Date de ieşire

Fişierul telegraf.out va conţine un singur număr, şi anume lungimea minimă (în secunde) necesară pentru transmiterea textului.

Restricții și precizări

• nici unul din cele $36$ de simboluri nu apare de mai mult de $10^6$ ori în textul considerat
• există cel puţin două simboluri cu număr de apariţii nenul
• $40\%$ dintre teste vor conţine maxim $16$ simboluri cu frecvenţă de apariţie nenulă.

Exemplu

telegraf.in

2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

telegraf.out

11

Explicație

Se constată că este optim să se transmită acest text folosind codificarea din Exemplul $1$, obţinând o lungime minimă a transmisiei de $11$ secunde.