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

Dupa mai multe incercari esuate de a castiga la Loto, WW decide sa renunte si sa se apuce de jocuri de noroc. A deprins repede experienta si chiar a inceput sa castige bani frumosi (sumele dobandite sunt strict confidentiale). Nu conteaza cum a reusit ca intr-un timp atat de scurt sa invete atat de multe, ce conteaza, insa, este ca zilele trecute WW a dat peste un joc destul de incurcat. El are in fata $M$ jetoane, puse unul langa celalalt, pe care sunt inscriptionate literele mici ale alfabetului englez (cate o litera pe fiecare jeton). El poate executa urmatoarea mutare asupra sirului: alege o subsecventa (de maxim $M$ litere) pe care o extrage, apoi alatura (daca exista) cele doua bucati ramase. Pentru ca jocul sa fie si mai palpitant, fiecare litera are o pondere $p{~i~}$. Mai mult, WW nu poate alege orice subsecventa, ci doar una aflata in lista de $N$ mutari valide (care se obtinue la inceputul jocului printr-un algoritm neinteresant). Cand WW a extras o anumita subsecventa el primeste un scor numeric egal cu suma ponderii fiecarei litere ce compune subsecventa.

Dupa mai multe incercari esuate de a castiga la Loto, _WW_ decide sa renunte si sa se apuce de jocuri de noroc. A deprins repede experienta si chiar a inceput sa castige bani frumosi (sumele dobandite sunt strict confidentiale). Nu conteaza cum a reusit ca intr-un timp atat de scurt sa invete atat de multe, ce conteaza, insa, este ca zilele trecute _WW_ a dat peste un joc destul de incurcat. El are in fata $M$ jetoane, puse unul langa celalalt, pe care sunt inscriptionate literele mici ale alfabetului englez (cate o litera pe fiecare jeton). El poate executa urmatoarea mutare asupra sirului: alege o subsecventa (de maxim $M$ litere) pe care o extrage, apoi alatura (daca exista) cele doua bucati ramase. Pentru ca jocul sa fie si mai palpitant, fiecare litera are o pondere $p[i]$. Mai mult, _WW_ nu poate alege orice subsecventa, ci doar una aflata in lista de $N$ mutari valide (care se obtinue la inceputul jocului printr-un algoritm neinteresant). Cand _WW_ a extras o anumita subsecventa el primeste un scor numeric egal cu suma ponderii fiecarei litere ce compune subsecventa.

h2. Cerinta

WW va pune la dispozitie sirul de jetoane, ponderile fiecarei litere, precum si lista cu mutarile valide. Va roaga sa-l ajutati a determina scorul maxim pe care poate sa-l obtina.

_WW_ va pune la dispozitie sirul de jetoane, ponderile fiecarei litere, precum si lista cu mutarile valide. Va roaga sa-l ajutati a determina scorul maxim pe care poate sa-l obtina.

h2. Date de intrare

h2. Date de iesire

Pe prima linie a fisierului $jetoane2.out$ se va afla numarul maxim cerut de WW.

Pe prima linie a fisierului $jetoane2.out$ se va afla numarul maxim cerut de _WW_.

h2. Restrictii
* $1$ ≤ $M$ ≤ $150$
* $1$ ≤ $N$ ≤ $200$
* toate literele din fisierul de intrare vor fi litere mici ale alfabetului englez

* pentru simplitatea si cursivitatea citirii enuntului WW se poate citi $Dublu V$

* pentru simplitatea si cursivitatea citirii enuntului _WW_ se poate citi $Dublu V$

h2. Exemplu