== 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 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.
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
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.
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.
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 ≤ N ≤ 170$}
* {$1 ≤ lungimea sirului initial ≤ 170$}
* $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 $30%$ din teste $N ≤ 9$
* pentru simplitatea si cursivitatea enuntului WW se poate citi _Dubluveu_
* pentru simplitatea si cursivitatea citirii enuntului _WW_ se poate citi $Dublu V$
h2. Exemplu
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
table(example). |_. jetoane2.in |_. jetoane2.out |_. explicatie |
| 5
a 2
b 5
c 3
d 1
e 4
aabcdee
5
ab
be
ae
acd
| 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$}.
| 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. |
== include(page="template/taskfooter" task_id="jetoane2") ==
