== 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 un numar de 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, din acest sir, 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 obtine 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.
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
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 $1000$, reprezentand ponderea fiecarei litere. Pe a doua linie se afla sirul initial de jetoane urmat, pe a treia linie, de numarul de mutari valide, $N$. Pe urmatoarele $N$ linii se afla cate un sir de maxim $10$ caractere, reprezentad descrierea unei mutari.
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
* {$1 ≤ N ≤ 170$}
* {$1 ≤ lungimea sirului initial ≤ 170$}
* 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$
* doua litere pot avea aceeasi pondere
* pentru $30%$ din teste $N ≤ 9$
* pentru simplitatea si cursivitatea enuntului WW se poate citi _Dubluveu_
h2. Exemplu
table(example). |_. jetoane2.in |_. jetoane2.out |_. explicatie |
| 5
a 2
b 5
c 3
d 1
e 4
table(example). |_. jetoane2.in |_. jetoane2.out |
|2 5 3 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
aabcdee
5
ab
be
ae
acd
| 19
| Initial sirul este "aabcdee". WW extragere intai sirul "cd" ("aab ee"),
obtinandu-se sirul "aabee" si costul 1+3=4. Urmatorea mutare este
extragerea sirului "be" ("aa e"), obtinandu-se sirul "aae" si costul
4+(5+4)=13. Ultima subsecventa extrasa este "ae", sirul devenind "a" si
costul final, 13+(2+4)=19. |
| 19 |
h3. Explicatie
Initial sirul este "{$aabcdee$}". WW extrage intai sirul "{$cd$}" ("{$aab ee$}"), obtinandu-se sirul "{$aabee$}" si costul {$1+3=4$}. Urmatorea mutare este extragerea sirului "{$be$}" ("{$aa e$}"), obtinandu-se sirul "{$aae$}" si costul {$4+(5+4)=13$}. Ultima subsecventa extrasa este "{$ae$}", sirul devenind "{$a$}" si costul final, {$13+(2+4)=19$}.
== include(page="template/taskfooter" task_id="jetoane2") ==
