== include(page="template/taskheader" task_id="strigat") ==

La insistentele aghiotantului sau Arthur, Tick s-a decis sa renunte la strigatul sau de lupta "Lingura". Tick vrea ca strigatul sau sa  fie cat mai inspaimantator pentru rafacatorii din oras. Tick stie ca exista $M$ cuvinte care ii sperie pe raufacatori si care daca se vor afla in cadrul strigatului sau provoaca un anumit grad de spaima. Se cunoaste pentru fiecare cuvant gradul de spaima pe care il provoaca {$A{~i~}$}. Gradul total de spaima al strigatului va fi {$A{~1~}*n{~1~} + A{~2~}*n{~2~} + ... + A{~M~}*n{~M~}$}, unde {$n{~i~}$} este numarul de aparitii al cunvatului $i$ in cadrul strigatului. Atentie aparitiile cuvintelor se pot suprapune.

La insistentele aghiotantului sau Arthur, Tick s-a decis sa renunte la strigatul sau de lupta "Lingura". Tick vrea ca strigatul sau sa fie cat mai inspaimantator pentru raufacatorii din oras. Tick stie ca exista $M$ cuvinte care ii sperie pe raufacatori si care daca se vor afla in cadrul strigatului sau provoaca un anumit grad de spaima. Se cunoaste pentru fiecare cuvant gradul de spaima pe care il provoaca {$A{~i~}$}. Gradul total de spaima al strigatului va fi {$A{~1~}*n{~1~} + A{~2~}*n{~2~} + ... + A{~M~}*n{~M~}$}, unde {$n{~i~}$} este numarul de aparitii al cunvatului $i$ in cadrul strigatului. Atentie aparitiile cuvintelor se pot suprapune.

h2. Cerinta

Ajutati-l pe Tick sa isi gaseasca strigat de lupta format din $N$ caractere si care provoaca un grad maxim de spaima.

Ajutati-l pe Tick sa isi gaseasca un strigat de lupta format din $N$ caractere si care provoaca un grad maxim de spaima.

h2. Date de intrare

Pe prima a fisierului de intrare $strigat.in$ se afla doua numere intregi $N$ si $M$ cu seminificatiile din enunt. Urmeaza apoi $M$ perechi de linii pe prima aflandu-se un cuvant, iar pe a doua gradul de spaima pe care il induce o aparitie a sa.

Pe prima linie a fisierului de intrare $strigat.in$ se afla doua numere intregi $N$ si $M$ cu semnificatiile din enunt. Urmeaza apoi $M$ perechi de linii pe prima aflandu-se un cuvant, iar pe a doua gradul de spaima pe care il induce o aparitie a sa.

h2. Date de iesire

h2. Exemplu
table(example). |_. strigat.in |_. strigat.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 2
aa
5
ab
6
| 16
aaab

|
h3. Explicatie

...

*aa* apare de $2$ ori(incepand cu prima respectiv cu a doua pozitie), *ab* apare o singura data deci spaima totala este {$5*2+6=16$}.
Nici un alt strigat nu poate atinge o valoare mai mare.
 

== include(page="template/taskfooter" task_id="strigat") ==

2027