Cerința

Emil are un mouse special, cu două rotițe de scroll. Pe fiecare rotiță de scroll el poate fixa câte o bandă circulară de cauciuc pe care sunt printate în format 3D caracterele utilizate frecvent pentru editare.

Apăsând vertical rotița de scroll în punctul ei cel mai înalt, caracterul aflat în punctul de apăsare va fi generat de către mouse. Astfel se pot edita diferite texte doar cu ajutorul mouse-ului. Ordinea în care sunt printate caracterele influențează viteza de tastare și energia consumată în procesul de editare a textelor. Efortul de trecere de la un caracter la următorul sau la anteriorul consumă o cantitate de energie egală cu o unitate. Apăsarea pe rotiță nu consumă energie. Emil vrea să afle care este cantitatea minimă de energie pe care trebuie să o consume pentru construirea unui text dat.

Date de intrare

Fișierul de intrare birot.in conține pe prima linie șirul de caractere printat pe banda de cauciuc de pe prima rotiță de scroll. Pe a doua linie se află șirul de caractere printat pe banda de cauciuc de pe a doua rotiță de scroll, iar pe a treia linie se afla textul care trebuie construit cu ajutorul mouse-ului.

Date de ieșire

Fișierul de ieșire birot.out va conține pe prima linie numărul reprezentând cantitatea minimă de energie ce trebuie consumată pentru construirea textului dat.

Restricții și precizări

• lungimile primelor două șiruri sunt egale și ≤ 90;
• în fiecare din primele două șiruri caracterele sunt distincte;
• primele două șiruri sunt formate din aceleași caractere, eventual așezate în altă ordine;
• lungimea șirului care trebuie construit este cel mult egală cu 10 000;
• orice caracter din șirul care trebuie construit se găsește în fiecare din primele două șiruri;
• caracterele care pot apărea în textul dat și pe benzile de cauciuc sunt caractere printabile, inclusiv caracterul spaţiu;
• inițial fiecare rotiță este așezată astfel încât primul caracter din șirul corespunzător ei să se afle deasupra, în poziția cea mai înaltă;
• benzile de cauciuc sunt astfel așezate pe rotițe încât împingând rotițele înspre înainte caracterele sunt parcurse, circular, în ordinea dată în șirurile citite.

Exemplu:

birot.in

abo-r
ao-br
bar-ba-ra

birot.out

7

Explicație