8. Aminokyseliny

Šandyna je šikovná bioinformatička a vo svojej práci často manipuluje RNA a DNA rôznych vírusov. Naposledy potrebovala izolovať sekvenciu istého Krutého Sveta-Paralyzujúceho vírusu. Žiaľ, pri pokuse sa jej to nepodarilo, miesto toho len izolovala \(n\) úsekov aminokyselín a nie presnú sekvenciu ktorú by potrebovala. Ale ešte nič nie je stratené! V laboratóriu biologickými čarami vie Šandyna spájať sekvencie, aby dostala RNA vírusu. Ale to nie je len tak, spájať genetické sekvencie. Niektoré sa pripájajú ťažšie než iné. Potrebuje preto zistiť ako ich čo najľahšie spojiť do chceného RNA. Pomôžte jej!

Úloha

Šandyna má reťazec \(T\), RNA vírusu ktorý chce zostaviť. Tiež už má \(n\) úsekov genetického kódu. Genetický kód si vieme zapísať ako reťazec malých písmen anglickej abecedy. Šandyna má tiež vzorky nukleidov reprezentovaných každým písmenom. Šandyna začína s prázdnou sekvenciou a tú výslednú by chcela zostrojiť pomocou týchto štyroch postupov:

• Na začiatok aktálnej sekvencie prilepí jeden nukleid (písmenko). Prilepenie nukleidu \(c\) má cenu \(cl_c \cdot |S|\) .

• Na koniec aktuálnej sekvencie prilepí jeden nukleid (písmenko). Prilepenie nukleidu \(c\) má cenu \(cr_c \cdot |S|\)

• Na začiatok aktuálnej sekvencie prilepí genetickú sekvenciu číslo \(i\) (\(1 \leq i \leq n\)). Prilepenie sekvencie má cenu \(kl_i \cdot |S|\)

• Na koniec aktuálnej sekvencie prilepí genetickú sekvenciu číslo \(i\) (\(1 \leq i \leq n\)). Prilepenie sekvencie má cenu \(kr_i \cdot |S|\)

Kde \(|S|\) je dĺžka aktuálnej sekvecie. Všimnime si, že pridať prvý nukleid/sekvenciu je vždy zadarmo.

Šandyna nevie vytvárať paralelne viac sekvencíí a potom ich prilepiť k sebe. Ako najlacnejšie môže vytvoriť správny genetický kód?

Formát vstupu

Na prvom riadku je číslo \(n\) - počet predom izolovaných sekvencií.

Na ďalších \(n\) riadkoch sú tieto sekvencie, \(p_1\) až \(p_n\), reprezentované ako reťazce malej anglickej abecedy.

Na ďalšom riadku je \(26\) medzerami oddelených cien pripojenia jediného nukleidu na začiatok: \(cl_a\), až \(cl_z\).

Na ďalšom riadku je \(26\) medzerami oddelených cien pripojenia jediného nukleidu na koniec: \(cr_a\), až \(cr_z\).

Na ďalšom riadku je \(n\) medzerami oddelených cien pripojenia genetických sekvencií na začiatok: \(kl_1\), až \(kl_n\)

Na ďalšom riadku je \(n\) medzerami oddelených cien pripojenia genetických sekvencií na koniec: \(kr_1\), až \(kr_n\)

A na poslednom riadku je reťazec \(T\) - genetická sekvencia ktorú Šandyna chce vytvoriť.

Formát výstupu

Vypíšte jediný riadok: najmenšiu cenu za ktorú vie Šandyna sekvenciu vytvoriť.

Hodnotenie

Vo všetkých vstupoch platia nasledovné limity:

• \(1 \leq |T| \leq 1\,000\)

• \(0 \leq n \leq 100\,000\)

• Všetky počiatočne izolované genetické sekvencie \(p_i\) majú dĺžku najviac \(100\).

• Všetky ceny sú medzi \(1\) a \(10^9\)

• Všetky reťazce obsahujú iba malé písmená anglickej abecedy

Sú \(4\) testovacie sady. V nich navyše platia nasledovné obmedzenia:

V sade \(2\) navyše platí \(|p_i| \leq 10\).

Príklady

Input:

0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
10 1 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26


abaca

Output:

15

Najlepšie je budovať sekvenciu odzadu. Cena je tak \(0 + 3\cdot 1 + 1\cdot 2 + 2 \cdot 3 + 1 \cdot 4 = 15\)

Input:

3
aba
ba
xy
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
3 2 1 3 5 9 10 11 11 9 9 8 7 6 5 1 33 22 11 90 1 1 2 3 5 8
1 2 3
1 1 1
abacaba

Output:

5

Šandyna by mala začať s nukleidom \(c\). Potom za cenu \(1\cdot 1 = 1\) by mala pripojiť sekvenciu ‘aba’ na začiatok a napokon tú istú sekvenciu aj na koniec (za cenu \(1\cdot 4 = 4\), keďže sekvencia po druhom kroku bola ‘abac’. Celková cena je teda \(5\).