== 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). O mutare valida este reprezentata de un sir de maxim $10$ caractere. 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). O mutare valida este reprezentata de un sir de maxim $7$ caractere. Cand WW a extras o anumita subsecventa el primeste un scor numeric egal cu suma ponderii fiecarei litere ce compune subsecventa.

h2. Cerinta

h2. Date de intrare

Pe prima linie a fisierului $jetoane2.in$ se afla $26$ de numere naturale, mai mici decat $10000$, reprezentand ponderea fiecarei litere. Pe a doua linie se afla $M$, numarul de jetoane, urmat, pe a treia linie, de sirul initial de jetoane (un sir de $M$ litere mici). Pe a patra linie se afla nr de mutari valide, $N$, iar pe urmatoarele $N$ linii se afla cate un sir de maxim $10$ caractere, reprezentad descrierea unei mutari.

Pe prima linie a fisierului $jetoane2.in$ se afla $26$ de numere naturale, mai mici decat $10000$, reprezentand ponderea fiecarei litere. Pe a doua linie se afla $M$, numarul de jetoane, urmat, pe a treia linie, de sirul initial de jetoane (un sir de $M$ litere mici). Pe a patra linie se afla nr de mutari valide, $N$, iar pe urmatoarele $N$ linii se afla cate un sir de maxim $7$ caractere, reprezentad descrierea unei mutari.

h2. Date de iesire

h2. Restrictii

* $1$ ≤ $M$, $N$ ≤ $150$

* $1$ ≤ $M$ ≤ $150$
* $1$ ≤ $N$ ≤ $200$

* toate literele din fisierul de intrare vor fi litere mici ale alfabetului englez

* doua litere pot avea aceeasi pondere
* pentru 40% din teste $1$ ≤ $M$, $N$ ≤ $50$

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